TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1993

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1993

Testing Hereditary Properties Efficiently on Average
Zitatschlüssel Report-350-1993
Autor Jens Gustedt and Angelika Steger
Buchtitel Orders, Algorithms and Applications, 1994
Seiten 100-116
Jahr 1993
Nummer 350
Herausgeber Vincent Bouchitté and Michel Morvan
Verlag Springer-Verlag
Serie Lecture Notes in Computer Science 831
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We use the quasi-ordering of substructure relations such as induced and weak subgraph, induced suborder, graph minor or subformula of a CNF formula to obtain recognition algorithms for hereditary properties that are fast on average. The ingredients needed besides inheritance are independence of the occurrence of small substructures in a random input and the existence of algorithms for recognition that are at most exponential.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe