TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

Testing Hereditary Properties Efficiently on Average
Citation key Report-350-1993
Author Jens Gustedt and Angelika Steger
Title of Book Orders, Algorithms and Applications, 1994
Pages 100-116
Year 1993
Number 350
Editor Vincent Bouchitté and Michel Morvan
Publisher Springer-Verlag
Series Lecture Notes in Computer Science 831
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe