Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
When Trees Grow Low: Shrubs and Fast MSO1
verfasst von : Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, Patrice Ossona de Mendez, Reshma Ramadurai
Erschienen in: Mathematical Foundations of Computer Science 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Recent characterization [9] of those graphs for which coloured MSO
2
model checking is fast raised the interest in the graph invariant called
tree-depth
. Looking for a similar characterization for (coloured) MSO
1
, we introduce the notion of
shrub-depth
of a graph class. To prove that MSO
1
model checking is fast for classes of bounded shrub-depth, we show that shrub-depth exactly characterizes the graph classes having interpretation in coloured trees of bounded height. We also introduce a common extension of cographs and of graphs with bounded shrub-depth —
m-partite cographs
(still of bounded clique-width), which are well quasi-ordered by the relation “is an induced subgraph of” and therefore allow polynomial time testing of hereditary properties.