A SAT Approach to Branchwidth

DOI10.1007/978-3-319-40970-2_12zbMath1475.68219OpenAlexW2465457706MaRDI QIDQ2818011

Sebastian Ordyniak, Stefan Szeider, Neha Lodha

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)

Related Items

Tangle bases: Revisited

Uses Software

• Treewidthlib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Satisfiability, branch-width and Tseitin tautologies
• Computing branchwidth via efficient triangulations and blocks
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Combinatorial Optimization
• Tour Merging via Branch-Decomposition
• A SAT Approach to Clique-Width
• On the Boolean-Width of a Graph: Structure and Applications
• A Local Search Algorithm for Branchwidth
• Encoding Treewidth into SAT
• Graphs, branchwidth, and tangles! Oh my!
• Finding Branch-Decompositions and Rank-Decompositions