The Complexity of Near-Optimal Graph Coloring
From MaRDI portal
Publication:4083458
DOI10.1145/321921.321926zbMath0322.05111WikidataQ89895272 ScholiaQ89895272MaRDI QIDQ4083458
David S. Johnson, Michael R. Garey
Publication date: 1976
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321921.321926
Related Items
Distributed algorithms for maximum cliques, Coloration de graphes : fondements et applications, On the chromatic number of graphs, Graph theory (algorithmic, algebraic, and metric problems), On approximating the minimum independent dominating set, Kneser's conjecture, chromatic number, and homotopy, On approximation problems related to the independent set and vertex cover problems, Applications of edge coverings by cliques, On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems, A better performance guarantee for approximate graph coloring, Coloring certain proximity graphs, Approximation algorithm for maximum edge coloring, Non-approximability of just-in-time scheduling, Extremal problems concerning Kneser-graphs, Clustering to minimize the maximum intercluster distance, Verifying nonrigidity, A graph coloring algorithm for large scale scheduling problems, On the complexity of H-coloring, The complexity of multicolouring, Maximum bipartite subgraphs of Kneser graphs, Structure preserving reductions among convex optimization problems, Complexity of dimension three and some related edge-covering characteristics of graphs, How well can a graph be n-colored?, Non deterministic polynomial optimization problems and their approximations, Discrete extremal problems, A note on the approximation of the MAX CLIQUE problem, The smallest hard-to-color graph, Optimization, approximation, and complexity classes, Finding approximate solutions to NP-hard problems by neural networks is hard, Quantifiers and approximation, A note on the complexity of the chromatic number problem, Zero knowledge and the chromatic number, The complexity of some problems related to GRAPH 3-COLORABILITY, Bidegree of graph and degeneracy number, The hardness of approximation: Gap location, Probabilistically checkable proofs and their consequences for approximation algorithms, On proving that a graph has no large clique: A connection with Ramsey theory, Routing a vehicle of capacity greater than one, The multichromatic numbers of some Kneser graphs, NP-completeness of a family of graph-colouring problems, Coloring graph products---a survey, Embedding a novel objective function in a two-phased local search for robust vertex coloring, Orthogonal representations over finite fields and the chromatic number of graphs, Graph Coloring Using Eigenvalue Decomposition, Unnamed Item, Local optimization of colorings of graphs, Unnamed Item, Worst-Case Analysis of Network Design Problem Heuristics
