License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.56
URN: urn:nbn:de:0030-drops-119177
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11917/
Gajarský, Jakub ;
Kreutzer, Stephan
Computing Shrub-Depth Decompositions
Abstract
Shrub-depth is a width measure of graphs which, roughly speaking, corresponds to the smallest depth of a tree into which a graph can be encoded. It can be thought of as a low-depth variant of clique-width (or rank-width), similarly as treedepth is a low-depth variant of treewidth. We present an fpt algorithm for computing decompositions of graphs of bounded shrub-depth. To the best of our knowledge, this is the first algorithm which computes the decomposition directly, without use of rank-width decompositions and FO or MSO logic.
BibTeX - Entry
@InProceedings{gajarsk_et_al:LIPIcs:2020:11917,
author = {Jakub Gajarsk{\'y} and Stephan Kreutzer},
title = {{Computing Shrub-Depth Decompositions}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {56:1--56:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11917},
URN = {urn:nbn:de:0030-drops-119177},
doi = {10.4230/LIPIcs.STACS.2020.56},
annote = {Keywords: shrub-depth, tree-model, decomposition, fixed-parameter tractability}
}
|
Keywords: |
|
shrub-depth, tree-model, decomposition, fixed-parameter tractability |
|
Collection: |
|
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.03.2020 |
