A short proof of the NP-completeness of minimum sum interval coloring
From MaRDI portal
Publication:2488233
DOI10.1016/j.orl.2004.07.006zbMath1067.05027OpenAlexW2003902428MaRDI QIDQ2488233
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
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