Improving the performance guarantee for approximate graph coloring
From MaRDI portal
Publication:3763600
DOI10.1145/2157.2158zbMath0627.68057OpenAlexW1982506822WikidataQ29399072 ScholiaQ29399072MaRDI QIDQ3763600
Publication date: 1983
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2157.2158
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (36)
CLAP: A New Algorithm for Promise CSPs ⋮ Efficient Vertex- and Edge-Coloring of Outerplanar Graphs ⋮ An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs ⋮ Matrix Relaxations in Combinatorial Optimization ⋮ On the Complexity of Scheduling to Optimize Average Response Time ⋮ On the complexity of H-coloring ⋮ Local-Global Phenomena in Graphs ⋮ Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function ⋮ An on-line graph coloring algorithm with sublinear performance ratio ⋮ Unnamed Item ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Distributed algorithms for maximum cliques ⋮ A better performance guarantee for approximate graph coloring ⋮ The smallest hard-to-color graph ⋮ Coloring bipartite hypergraphs ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ Linear Index Coding via Semidefinite Programming ⋮ A still better performance guarantee for approximate graph coloring ⋮ The greedy algorithm is optimal for on-line edge coloring ⋮ A simple algorithm for 4-coloring 3-colorable planar graphs ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Unnamed Item ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ The allocation problem in hardware design ⋮ New Tools for Graph Coloring ⋮ Three-quarter approximation for the number of unused colors in graph coloring ⋮ Combinatorial optimization in system configuration design ⋮ Unnamed Item ⋮ Worst case analysis of a graph coloring algorithm ⋮ Hardness of Rainbow Coloring Hypergraphs ⋮ Finding Pseudorandom Colorings of Pseudorandom Graphs ⋮ The maximum clique problem ⋮ Decomposing a set of points into chains, with applications to permutation and circle graphs
This page was built for publication: Improving the performance guarantee for approximate graph coloring
