Graph coloring with rejection

DOI10.1016/j.jcss.2010.06.016zbMath1213.05077MaRDI QIDQ632809

Gerhard J. Woeginger, Leah Epstein, Asaf Levin

Publication date: 28 March 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.016

zbMATH Keywords

graph coloring; online algorithms; approximation algorithms

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68W27: Online algorithms; streaming algorithms

Related Items

Online hypergraph coloring with rejection, The online \(k\)-server problem with rejection, Online file caching with rejection penalties, On Variants of File Caching

Cites Work

• Unnamed Item
• Improved performance of the greedy algorithm for partial cover
• The maximum k-colorable subgraph problem for chordal graphs
• On chain and antichain families of a partially ordered set
• The greedy algorithm is optimal for on-line edge coloring
• On-line coloring \(k\)-colorable graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The NP-completeness column: an ongoing guide
• On-line and first fit colorings of graphs
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Graph Classes: A Survey
• A General Approximation Technique for Constrained Forest Problems