Record link: 
http://hdl.handle.net/20.500.12708/57264
-
Title: 
Combining Treewidth and Backdoors for CSP
en
Citation: 
Ganian, R., Ramanujan, M. S., & Szeider, S. (2017). Combining Treewidth and Backdoors for CSP. In H. Vollmer & B. Vallée (Eds.), 34th Symposium on Theoretical Aspects of Computer Science (pp. 429–445). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. https://doi.org/10.4230/LIPIcs.STACS.2017.36
-
Publisher DOI: 
10.4230/LIPIcs.STACS.2017.36
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Ganian, Robert 
Ramanujan, M. Sridharan 
Szeider, Stefan 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
34th Symposium on Theoretical Aspects of Computer Science 
-
ISBN: 
978-3-95977-028-6
-
Volume: 
66
-
Date (published): 
2017
-
Event name: 
34th International Symposium on Theoretical Aspects of Computer Science 
en
Event date: 
8-Mar-2017 - 11-Mar-2017
-
Event place: 
Hannover, Germany
-
Number of Pages: 
17
-
Publisher: 
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
-
Publisher: 
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl
-
Keywords: 
Constraint Satisfaction; Algorithms and data structures; Fixed Parameter Tractability
-
Abstract: 
Decomposition width parameters such as treewidth provide a measurement on the complexity of a graph. Finding a decomposition of smallest width is itself NP-hard but lends itself to a SAT-based solution. Previous work on treewidth, branchwidth and clique-width indicates that identifying a suitable characterization of the considered decomposition method is key for a practically feasible SAT-encoding. In this paper we study SAT-encodings for the decomposition width parameters special treewidth and pathwidth. In both cases we develop SAT-encodings based on two different characterizations. In particular, we develop two novel characterizations for special treewidth based on parti- tions and elimination orderings. We empirically obtained SAT-encodings.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Informatik
Mathematik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

221
checked on Nov 23, 2023

Google ScholarTM

Check