SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS

DOI10.1142/S1793830910000693zbMath1201.05037OpenAlexW2146511660MaRDI QIDQ3063603

Rajiv Gandhi, Rajiv Raman, Bradford Jun. Greening, Sriram V. Pemmaraju

Publication date: 15 December 2010

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830910000693

zbMATH Keywords

approximation algorithmNP-completeinterval graphshypo-coloringsub-coloring

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Approximation algorithms (68W25)

Related Items (1)

On the algorithmic aspects of strong subcoloring

Cites Work

• Unnamed Item
• Unnamed Item
• More about subcolorings
• Linear-time recognition of circular-arc graphs
• A hypocoloring model for batch scheduling
• The subchromatic number of a graph
• A short proof of the NP-completeness of minimum sum interval coloring
• Backfilling with lookahead to optimize the packing of parallel jobs
• The Complexity of Coloring Circular Arcs and Chords
• Graph Subcolorings: Complexity and Algorithms
• On the Complexity of Distributed Network Decomposition

This page was built for publication: SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS