Shrub-depth: Capturing Height of Dense Graphs

J 2019

Shrub-depth: Capturing Height of Dense Graphs

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

Základní údaje

Originální název

Shrub-depth: Capturing Height of Dense Graphs

Autoři

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

Vydání

Logical Methods in Computer Science, BRAUNSCHWEIG, LOGICAL METHODS COMPUTER SCIENCE E V, 2019, 1860-5974

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 0.672

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/19:00108273

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

tree-depth; clique-width; shrub-depth; MSO logic; transduction

Štítky

formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 16. 4. 2020 09:41, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower omega levels of the MSO1 transduction hierarchy of simple graphs.

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

Citovat

GANIAN, Robert; Petr HLINĚNÝ; Jaroslav NEŠETŘIL; Jan OBDRŽÁLEK a Patrice OSSONA DE MENDEZ. Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science. BRAUNSCHWEIG: LOGICAL METHODS COMPUTER SCIENCE E V, 2019, roč. 15, č. 1, s. "7:1"-"7:25", 25 s. ISSN 1860-5974. Dostupné z: https://doi.org/10.23638/LMCS-15(1:7)2019.

@article{1646045,
   author = {Ganian, Robert and Hliněný, Petr and Nešetřil, Jaroslav and Obdržálek, Jan and Ossona de Mendez, Patrice},
   article_location = {BRAUNSCHWEIG},
   article_number = {1},
   doi = {https://doi.org/10.23638/LMCS-15(1:7)2019},
   keywords = {tree-depth; clique-width; shrub-depth; MSO logic; transduction},
   language = {eng},
   issn = {1860-5974},
   journal = {Logical Methods in Computer Science},
   title = {Shrub-depth: Capturing Height of Dense Graphs},
   url = {https://lmcs.episciences.org/5149},
   volume = {15},
   year = {2019}
}

TY  - JOUR
ID  - 1646045
AU  - Ganian, Robert - Hliněný, Petr - Nešetřil, Jaroslav - Obdržálek, Jan - Ossona de Mendez, Patrice
PY  - 2019
TI  - Shrub-depth: Capturing Height of Dense Graphs
JF  - Logical Methods in Computer Science
VL  - 15
IS  - 1
SP  - "7:1"-"7:25"
EP  - "7:1"-"7:25"
PB  - LOGICAL METHODS COMPUTER SCIENCE E V
SN  - 18605974
KW  - tree-depth
KW  - clique-width
KW  - shrub-depth
KW  - MSO logic
KW  - transduction
UR  - https://lmcs.episciences.org/5149
L2  - https://lmcs.episciences.org/5149
N2  - The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower omega levels of the MSO1 transduction hierarchy of simple graphs.
ER  -

GANIAN, Robert; Petr HLINĚNÝ; Jaroslav NEŠETŘIL; Jan OBDRŽÁLEK a Patrice OSSONA DE MENDEZ. Shrub-depth: Capturing Height of Dense Graphs. \textit{Logical Methods in Computer Science}. BRAUNSCHWEIG: LOGICAL METHODS COMPUTER SCIENCE E V, 2019, roč.~15, č.~1, s.~''7:1''-''7:25'', 25 s. ISSN~1860-5974. Dostupné z: https://doi.org/10.23638/LMCS-15(1:7)2019.

Přehled o publikaci