Graph coloring with rejection

DOI10.1016/J.JCSS.2010.06.016MaRDI QIDQ632809zbMATH OpenOpenAlexFDO

Authors Leah Epstein, Asaf Levin, Gerhard J. Woeginger

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

online algorithmsapproximation algorithmsgraph coloring

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Graph Coloring with Rejection
• Online hypergraph coloring with rejection
• Batch coloring of graphs
• Batch Coloring of Graphs
• Lower bounds for on-line graph coloring

Cites work

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

Cited in

(5)

• Online file caching with rejection penalties
• The online \(k\)-server problem with rejection
• On variants of file caching
• Online hypergraph coloring with rejection
• Graph Coloring with Rejection

This page was built for publication: Graph coloring with rejection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q632809)