Approximability Distance in the Space of H-Colourability Problems

DOI10.1007/978-3-642-03351-3_11MaRDI QIDQ3392945zbMATH OpenOpenAlexFDO

Authors Tommy Färnqvist, Peter Jonsson, Johan Thapper

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

zbMATH Keywords

computational complexityoptimisationgraph homomorphismapproximabilitygraph \(H\)-colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Approximation Algorithms for Graph Homomorphism Problems
• An approximability-related parameter on graphs -- properties and applications
• Properties of an approximability-related parameter on circular complete graphs
• Improved Inapproximability Results for Maximum k-Colorable Subgraph
• Improved inapproximability results for maximum \(k\)-colorable subgraph

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 1332666 (Why is no real title available?)
• scientific article; zbMATH DE number 1416059 (Why is no real title available?)
• A note on bipartite subgraphs of triangle-free regular graphs
• Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
• Approximation Algorithms for Graph Homomorphism Problems
• Bipartite density of cubic graphs
• Bipartite subgraphs
• Cliques in random graphs
• Edges in graphs with large girth
• Every 2-CSP allows nontrivial approximation
• Extremal bipartite subgraphs of cubic triangle-free graphs
• Fractional covering by cuts
• Graph Theory and Probability
• Homomorphisms from sparse graphs with large girth.
• How to Round Any CSP
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• MAX k‐CUT and approximating the chromatic number of random graphs
• On approximate graph colouring and MAX-k-CUT algorithms based on the -function
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• The chromatic number of random graphs
• The chromatic number of random graphs
• The concentration of the chromatic number of random graphs

Cited in

(4)

• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Approximation Algorithms for Graph Homomorphism Problems
• An approximability-related parameter on graphs -- properties and applications
• Properties of an approximability-related parameter on circular complete graphs

This page was built for publication: Approximability Distance in the Space of H-Colourability Problems

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