Technical Report 350-1993

Title

Testing Hereditary Properties Efficiently on Average

Authors

Jens Gustedt and Angelika Steger

Publication

Springer, Orders, Algorithms and Applications", series = , ed. Vincent Bouchitté and Michel Morvan, 1994, pp. 100-116

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

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.