A SAT approach to branchwidth

DOI10.1007/978-3-319-40970-2_12MaRDI QIDQ2818011zbMATH OpenOpenAlexFDO

Authors Neha Lodha, Sebastian Ordyniak, Stefan Szeider

Publication date 5 September 2016

Published in Theory and Applications of Satisfiability Testing – SAT 2016 (Search for Journal in Brave)

Full work available at URL http://eprints.whiterose.ac.uk/147995/1/main.pdf

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational aspects of satisfiability (68R07)

Recommendations

• A SAT approach to branchwidth
• SAT-encodings for special treewidth and pathwidth
• SAT-encodings for treecut width and treedepth
• SAT-based local improvement for finding tree decompositions of small width
• Theory and Applications of Satisfiability Testing

Cites work

• scientific article; zbMATH DE number 1990711 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• A local search algorithm for branchwidth
• Call routing and the ratcatcher
• Combinatorial optimization. Packing and covering
• Computing branchwidth via efficient triangulations and blocks
• Encoding Treewidth into SAT
• Finding Branch-Decompositions and Rank-Decompositions
• Graph minors. X: Obstructions to tree-decomposition
• Graphs, branchwidth, and tangles! Oh my!
• Logic, graphs, and algorithms
• On the Boolean-width of a graph: structure and applications
• Satisfiability, branch-width and Tseitin tautologies
• Tour merging via branch-decomposition

Cited in

(11)

• SAT-encodings for treecut width and treedepth
• Satisfiability, branch-width and Tseitin tautologies
• Constructive linear time algorithms for branchwidth
• Fast FPT-approximation of branchwidth
• A SAT approach to branchwidth
• Tangle bases: Revisited
• ESLIM: Circuit minimization with SAT based local improvement
• Logics in Artificial Intelligence
• SAT-based local improvement for finding tree decompositions of small width
• SAT-encodings for special treewidth and pathwidth
• Theory and Applications of Satisfiability Testing

Describes a project that uses

Uses Software

• Treewidthlib

This page was built for publication: A SAT approach to branchwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2818011)