Large hypertree width for sparse random hypergraphs

DOI10.1007/s10878-013-9704-yzbMath1350.90035MaRDI QIDQ2343976

Tian Liu, Ke Xu, Chaoyi Wang

Publication date: 11 May 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9704-y

zbMATH Keywords

constraint satisfaction; hypertree width; random hypergraphs; model RB; model RD

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

Related Items

Fractional Edge Cover Number of Model RB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent dominating sets in regular graphs
• A general model and thresholds for random constraint satisfaction problems
• Roman domination on strongly chordal graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Hypertree decompositions and tractable queries
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Tree clustering for constraint networks
• Decomposing constraint satisfaction problems using database techniques
• Treewidth. Computations and approximations
• Conjunctive query containment revisited
• A comparison of structural CSP decomposition methods
• Algebraic connectivity of an even uniform hypergraph
• A note on optimal pebbling of hypercubes
• Many hard examples in exact phase transitions
• Hypertree width and related hypergraph invariants
• Generating hard satisfiability problems
• Rank-width of random graphs
• Two Hardness Results on Feedback Vertex Sets
• The complexity of acyclic conjunctive queries
• On the Threshold of Having a Linear Treewidth in Random Graphs
• A Note on Treewidth in Random Graphs