The Complexity of Near-Optimal Graph Coloring
From MaRDI portal
Publication:4083458
DOI10.1145/321921.321926zbMath0322.05111OpenAlexW2025904765WikidataQ89895272 ScholiaQ89895272MaRDI QIDQ4083458
Michael R. Garey, David S. Johnson
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
Bidegree of graph and degeneracy number, Worst-case analysis of a new heuristic for the travelling salesman problem, Worst-Case Analysis of Network Design Problem Heuristics, CLAP: A New Algorithm for Promise CSPs, Topology and Adjunction in Promise Constraint Satisfaction, The hardness of approximation: Gap location, Small Promise CSPs that reduce to large CSPs, Probabilistically checkable proofs and their consequences for approximation algorithms, A graph coloring algorithm for large scale scheduling problems, On proving that a graph has no large clique: A connection with Ramsey theory, Coloration de graphes : fondements et applications, On the complexity of H-coloring, The complexity of multicolouring, Maximum bipartite subgraphs of Kneser graphs, Complexity of Coloring Random Graphs, Routing a vehicle of capacity greater than one, Coloring graph products---a survey, Graph Coloring Using Eigenvalue Decomposition, A supernodal formulation of vertex colouring with applications in course timetabling, Unnamed Item, Average-case complexity of backtrack search for coloring sparse random graphs, Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank, Structure preserving reductions among convex optimization problems, Complexity of dimension three and some related edge-covering characteristics of graphs, An approximation algorithm for 3-Colourability, Unnamed Item, Coloring k-colorable graphs in constant expected parallel time, Deciding 3-colourability in less than O(1.415n) steps, Near-linear convergence of the random Osborne algorithm for matrix balancing, How well can a graph be n-colored?, Unnamed Item, Non deterministic polynomial optimization problems and their approximations, Discrete extremal problems, Quantum annealing of the graph coloring problem, Local optimization of colorings of graphs, Distributed algorithms for maximum cliques, A better performance guarantee for approximate graph coloring, Coloring certain proximity graphs, Randomly colouring graphs (a combinatorial view), On percolation and ‐hardness, A note on the approximation of the MAX CLIQUE problem, The smallest hard-to-color graph, On the computational complexity of centers locating in a graph, Optimization, approximation, and complexity classes, Finding approximate solutions to NP-hard problems by neural networks is hard, Embedding a novel objective function in a two-phased local search for robust vertex coloring, Quantifiers and approximation, On the chromatic number of graphs, A note on the complexity of the chromatic number problem, Graph theory (algorithmic, algebraic, and metric problems), Unnamed Item, On the triangle clique cover and \(K_t\) clique cover problems, Approximation algorithm for maximum edge coloring, 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, Zero knowledge and the chromatic number, Applications of edge coverings by cliques, The complexity of some problems related to GRAPH 3-COLORABILITY, NP-completeness of a family of graph-colouring problems, Non-approximability of just-in-time scheduling, Orthogonal representations over finite fields and the chromatic number of graphs, The multichromatic numbers of some Kneser graphs, On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems, Extremal problems concerning Kneser-graphs, Clustering to minimize the maximum intercluster distance, Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}), Verifying nonrigidity
