A short proof of the NP-completeness of minimum sum interval coloring

DOI10.1016/j.orl.2004.07.006zbMath1067.05027OpenAlexW2003902428MaRDI QIDQ2488233

Dániel Marx

Publication date: 25 August 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.07.006

zbMATH Keywords

Computational complexityInterval graphGraph coloringChromatic sumMinimum sum coloring

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

The transportation problem with conflicts ⋮ Maximum cut on interval graphs of interval count four is NP-complete ⋮ Complexity of maximum cut on interval graphs ⋮ Minimum entropy combinatorial optimization problems ⋮ SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS ⋮ On the approximability of time disjoint walks ⋮ Minimum entropy coloring

Cites Work

• Unnamed Item
• On chromatic sums and distributed resource allocation
• The chromatic sum of a graph: history and recent developments
• An Efficient Test for Circular-Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Minimum Color Sum of Bipartite Graphs
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees

This page was built for publication: A short proof of the NP-completeness of minimum sum interval coloring