Batch Coloring Flat Graphs and Thin

DOI10.1007/978-3-540-69903-3_19zbMath1155.68578OpenAlexW2130766066MaRDI QIDQ3512459

Magnús M. Halldórsson, Hadas Shachnai

Publication date: 15 July 2008

Published in: Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69903-3_19

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Batch Coloring Flat Graphs and Thin, Max-coloring paths: tight bounds and extensions, Bounded max-colorings of graphs, Clique Clustering Yields a PTAS for max-Coloring Interval Graphs, On the max coloring problem, Approximating the max-edge-coloring problem, Clique clustering yields a PTAS for max-coloring interval graphs, Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A coloring problem for weighted graphs
• On the efficiency of polynomial time approximation schemes
• Weighted coloring: further complexity and approximability results
• On chromatic sums and distributed resource allocation
• Batch Coloring Flat Graphs and Thin
• Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
• Approximation algorithms for NP-complete problems on planar graphs
• Sum Multicoloring of Graphs
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• On the Max Coloring Problem
• Approximation and Online Algorithms
• Automata, Languages and Programming