Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Record link: 
http://hdl.handle.net/20.500.12708/57266
-
Title: 
SAT-Encodings for Special Treewidth and Pathwidth
-
Citation: 
Lodha, N., Ordyniak, S., & Szeider, S. (2017). SAT-Encodings for Special Treewidth and Pathwidth. In Theory and Applications of Satisfiability Testing – SAT 2017 (pp. 429–445). Springer International Publishing AG 2017. https://doi.org/10.1007/978-3-319-66263-3_27
-
Publisher DOI: 
10.1007/978-3-319-66263-3_27
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Authors: 
Lodha, Neha 
Ordyniak, Sebastian 
Szeider, Stefan 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Theory and Applications of Satisfiability Testing – SAT 2017 
-
Date (published): 
2017
-
Number of Pages: 
17
-
Publisher: 
Springer International Publishing AG 2017
-
Peer reviewed: 
Yes
-
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-en...
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Informatik
Mathematik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

219
checked on Nov 23, 2023

Google ScholarTM

Check