Fractional Edge Cover Number of Model RB
From MaRDI portal
Publication:4632176
DOI10.1007/978-3-319-39817-4_11zbMath1475.68349OpenAlexW2478661108MaRDI QIDQ4632176
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
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
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
