Approximating fractional hypertree width

DOI10.1145/1721837.1721845MaRDI QIDQ2930305zbMATH OpenOpenAlexFDO

Authors Dániel Marx

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

constraint satisfactionfractional hypertree widthtreewidth

Mathematics Subject Classification ID

Distance in graphs (05C12) Hypergraphs (05C65) Fractional graph theory, fuzzy graph theory (05C72) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Approximating fractional hypertree width
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Computing hypergraph width measures exactly
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries

Cited in

(28)

• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• Efficiently enumerating minimal triangulations
• Structural tractability of enumerating CSP solutions
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• Computing partial hypergraphs of bounded width
• Structural tractability of counting of solutions to conjunctive queries
• Tractability in constraint satisfaction problems: a survey
• Structural decompositions for problems with global constraints
• Approximating width parameters of hypergraphs with excluded minors
• Covers of Query Results
• Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
• Minor-matching hypertree width
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• Approximating fractional hypertree width
• HyperBench. A benchmark and tool for hypergraphs and empirical findings
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• Tractable structures for constraint satisfaction with truth tables
• Approximating acyclicity parameters of sparse hypergraphs
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• A backtracking-based algorithm for hypertree decomposition
• The complexity of conservative valued CSPs
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
• FPT approximation of generalised hypertree width for bounded intersection hypergraphs
• Approximately counting answers to conjunctive queries with disequalities and negations
• Tractable conjunctive queries over static and dynamic relations
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• FPT approximation of generalised hypertree width for bounded intersection hypergraphs

This page was built for publication: Approximating fractional hypertree width

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