Approximability Distance in the Space of H-Colourability Problems
From MaRDI portal
Publication:3392945
DOI10.1007/978-3-642-03351-3_11zbMath1248.68376OpenAlexW1549776389MaRDI QIDQ3392945
Johan Thapper, Peter Jonsson, Tommy Färnqvist
Publication date: 18 August 2009
Published in: Computer Science - Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_11
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (1)
Cites Work
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Edges in graphs with large girth
- The concentration of the chromatic number of random graphs
- Homomorphisms from sparse graphs with large girth.
- Bipartite density of cubic graphs
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Bipartite subgraphs
- Graph Theory and Probability
- A note on bipartite subgraphs of triangle-free regular graphs
- Fractional covering by cuts
- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
- On the power of unique 2-prover 1-round games
- Approximation Algorithms for Graph Homomorphism Problems
- Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph
- Largest bipartite subgraphs in triangle-free graphs with maximum degree three
- Extremal bipartite subgraphs of cubic triangle-free graphs
- Cliques in random graphs
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- How to Round Any CSP
- Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- MAX k‐CUT and approximating the chromatic number of random graphs
- Every 2-CSP allows nontrivial approximation
- The chromatic number of random graphs
- The chromatic number of random graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximability Distance in the Space of H-Colourability Problems
