A still better performance guarantee for approximate graph coloring
From MaRDI portal
Publication:1209311
DOI10.1016/0020-0190(93)90246-6zbMath0768.68043OpenAlexW2153663865WikidataQ56269092 ScholiaQ56269092MaRDI QIDQ1209311
Publication date: 16 May 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90246-6
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
Towards optimal lower bounds for clique and chromatic number., Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring, Probabilistically checkable proofs and their consequences for approximation algorithms, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Coloration de graphes : fondements et applications, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, Approximating the independence number via the \(\vartheta\)-function, Selection of programme slots of television channels for giving advertisement: a graph theoretic approach, Matrix-Free Convex Optimization Modeling, New approximation results on graph matching and related problems, Flexible coloring, Randomly colouring graphs (a combinatorial view), Non-clairvoyant scheduling with conflicts for unit-size jobs, Minimum clique partition in unit disk graphs, Inapproximability and approximability of minimal tree routing and coloring, An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem, Partition into cliques for cubic graphs: Planar case, complexity and approximation, An ant-based algorithm for coloring graphs, On the chromatic number of non-sparse random intersection graphs, On the probabilistic minimum coloring and minimum \(k\)-coloring, Approximating Independent Set and Coloring in Random Uniform Hypergraphs, Approximation of min coloring by moderately exponential algorithms, Combinatorial filter reduction: special cases, approximation, and fixed-parameter tractability, “Rent-or-Buy” Scheduling and Cost Coloring Problems, All structured programs have small tree width and good register allocation, Differential approximation algorithms for some combinatorial optimization problems, Zero knowledge and the chromatic number, Priority algorithms for graph optimization problems, Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks, Heuristics for semirandom graph problems
Cites Work
