A backtracking-based algorithm for hypertree decomposition

DOI10.1145/1412228.1412229MaRDI QIDQ5406168zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Georg Gottlob, Marko Samer

Publication date 1 April 2014

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1412228.1412229

zbMATH Keywords

constraint satisfactionhypertree decomposition

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1834638
• Hypertree decompositions and tractable queries
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Approximating fractional hypertree width

Cited in

(11)

• Fast and parallel decomposition of constraint satisfaction problems
• Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
• An Iterative Heuristic Algorithm for Tree Decomposition
• Minor-matching hypertree width
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• scientific article; zbMATH DE number 1834638 (Why is no real title available?)
• HyperBench. A benchmark and tool for hypergraphs and empirical findings
• Uniform Constraint Satisfaction Problems and Database Theory
• Graph-Theoretic Concepts in Computer Science
• Computing optimal hypertree decompositions with SAT
• Fast parallel hypertree decompositions in logarithmic recursion depth

This page was built for publication: A backtracking-based algorithm for hypertree decomposition

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