Fractional Edge Cover Number of Model RB

DOI10.1007/978-3-319-39817-4_11zbMath1475.68349OpenAlexW2478661108MaRDI QIDQ4632176

Tian Liu

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_11

zbMATH Keywords

hardnessfractional edge coverModel RB

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Uses Software

• BHOSLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A general model and thresholds for random constraint satisfaction problems
• 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
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Treewidth. Computations and approximations
• Large hypertree width for sparse random hypergraphs
• 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
• Constraint solving via fractional edge covers
• On the Threshold of Having a Linear Treewidth in Random Graphs
• A Note on Treewidth in Random Graphs
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries