GANIAN, Robert, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Jaroslav NEŠETŘIL, Patrice OSSONA DE MENDEZ a Reshma RAMADURAI. When Trees Grow Low: Shrubs and Fast MSO1. In Math Foundations of Computer Science MFCS 2012. 7464. vyd. Německo: Lecture Notes in Computer Science, Springer-Verlag. s. 419-430. ISBN 978-3-642-32588-5. doi:10.1007/978-3-642-32589-2_38. 2012.
Další formáty:   BibTeX LaTeX RIS
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
Originální 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 0302-9743
Doi http://dx.doi.org/10.1007/978-3-642-32589-2_38
Klíčová slova anglicky tree-depth; shrub-depth; MSO model checking
Štítky formela-conference
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 23. 4. 2013 13:19.
Anotace
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 VaVNá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 MUNá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 MUNá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
VytisknoutZobrazeno: 29. 3. 2024 09:40