When Trees Grow Low: Shrubs and Fast MSO1

Logo poskytovatele

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Když stromy nízké: Keře a rychlá MSO1
Autoři

GANIAN Robert HLINĚNÝ Petr OBDRŽÁLEK Jan NEŠETŘIL Jaroslav OSSONA DE MENDEZ Patrice RAMADURAI Reshma

Rok publikování 2012
Druh Článek ve sborníku
Konference Math Foundations of Computer Science MFCS 2012
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1007/978-3-642-32589-2_38
Obor Informatika
Klíčová slova tree-depth; shrub-depth; MSO model checking
Popis Recent characterization [9] of those graphs for which coloured MSO2 model checking is fast raised the interest in the graph invariant called tree-depth. Looking for a similar characterization for (coloured) MSO1, we introduce the notion of shrub-depth of a graph class. To prove that MSO1 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info