| GANIAN, Robert, Petr HLINĚNÝ, Jaroslav NEŠETŘIL, Jan OBDRŽÁLEK and Patrice OSSONA DE MENDEZ. Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science. BRAUNSCHWEIG: LOGICAL METHODS COMPUTER SCIENCE E V, 2019, vol. 15, No 1, p. "7:1"-"7:25", 25 pp. ISSN 1860-5974. Available from: https://dx.doi.org/10.23638/LMCS-15(1:7)2019. |
Other formats:
BibTeX
LaTeX
RIS
@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 = {http://dx.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 and 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, vol.~15, No~1, p.~''7:1''-''7:25'', 25 pp. ISSN~1860-5974. Available from: https://dx.doi.org/10.23638/LMCS-15(1:7)2019.
|
