A SAT approach to branchwidth

DOI10.1145/3326159MaRDI QIDQ4972153zbMATH OpenOpenAlexWikidataFDO

Authors Neha Lodha, Sebastian Ordyniak, Stefan Szeider

Publication date 22 November 2019

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

heuristic searchSAT encodingbranchwidthcarving-width

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Hypergraphs (05C65) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational aspects of satisfiability (68R07)

Recommendations

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

Cited in

(10)

• SAT-encodings for treecut width and treedepth
• Satisfiability, branch-width and Tseitin tautologies
• Constructive linear time algorithms for branchwidth
• Fast FPT-approximation of branchwidth
• SAT-boosted tabu search for coloring massive graphs
• A SAT approach to branchwidth
• 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

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 Q4972153)