GANIAN, Robert, Neha LODHA, Sebastian ORDYNIAK and Stefan SZEIDER. SAT-Encodings for Treecut Width and Treedepth. Online. In Stephen G. Kobourov and Henning Meyerhenke. ALENEX 2019. USA: SIAM, 2019, p. 117-129. ISBN 978-1-61197-549-9. Available from: https://dx.doi.org/10.1137/1.9781611975499.10.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name SAT-Encodings for Treecut Width and Treedepth
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Neha LODHA (356 India), Sebastian ORDYNIAK (276 Germany) and Stefan SZEIDER (40 Austria).
Edition USA, ALENEX 2019, p. 117-129, 13 pp. 2019.
Publisher SIAM
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
RIV identification code RIV/00216224:14330/19:00113720
Organization unit Faculty of Informatics
ISBN 978-1-61197-549-9
ISSN 2164-0300
Doi http://dx.doi.org/10.1137/1.9781611975499.10
Keywords in English Parameterized Complexity
Tags core_A, firank_A
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 14/5/2020 10:43.
Abstract
The decomposition of graphs is a prominent algorithmic task with numerous applications in computer science. A graph decomposition method is typically associated with a width parameter (such as treewidth) that indicates how well the given graph can be decomposed. Many hard (even #P-hard) algorithmic problems can be solved efficiently if a decomposition of small width is provided; the runtime, however, typically depends exponentially on the decomposition width. Finding an optimal decomposition is itself an NP-hard task. In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters tree-cut width and treedepth. These two parameters have recently gained a lot of attention in the theoretical research community as they offer the algorithmic advantage over treewidth by supporting so-called fixed-parameter algorithms for certain problems that are not fixed-parameter tractable with respect to treewidth. However, the existing research has mostly been theoretical. A main obstacle for any practical or experimental use of these two width parameters is the lack of any practical or implemented algorithm for actually computing the associated decompositions. We address this obstacle by providing the first practical decomposition algorithms.
PrintDisplayed: 18/9/2024 09:28