D 2012

When Trees Grow Low: Shrubs and Fast MSO1

GANIAN, Robert, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Jaroslav NEŠETŘIL, Patrice OSSONA DE MENDEZ et. al.

Základní údaje

Originální název

When Trees Grow Low: Shrubs and Fast MSO1

Název česky

Když stromy nízké: Keře a rychlá MSO1

Autoři

GANIAN, Robert (840 Spojené státy, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí), Jan OBDRŽÁLEK (203 Česká republika, domácí), Jaroslav NEŠETŘIL (203 Česká republika), Patrice OSSONA DE MENDEZ (250 Francie) a Reshma RAMADURAI (356 Indie, domácí)

Vydání

7464. vyd. Německo, Math Foundations of Computer Science MFCS 2012, od s. 419-430, 12 s. 2012

Nakladatel

Lecture Notes in Computer Science, Springer-Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Slovensko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/12:00057596

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-32588-5

ISSN

DOI

Klíčová slova anglicky

tree-depth; shrub-depth; MSO model checking

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 23. 4. 2013 13:19, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

GBP202/12/G061, projekt VaV
Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky
MUNI/A/0758/2011, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0914/2009, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty