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

被引：17
作者：
Marx, D [1 ]
机构：
[1] Budapest Univ Technol & Econ, Dept Comp Sci & Informat Theory, H-1521 Budapest, Hungary
来源：
OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 04期
基金：
匈牙利科学研究基金会;
关键词：
computational complexity; graph coloring; minimum sum coloring; chromatic sum; interval graph;
D O I：
10.1016/j.orl.2004.07.006
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In the minimum sum coloring problem we have to assign positive integers to the vertices of a graph in such a way that neighbors receive different numbers and the sum of the numbers is minimized. Szkalicki has shown that minimum sum coloring is NP-hard for interval graphs. Here we present a simpler proof of this result. (c) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：382 / 384
页数：3
相关论文
共 10 条
1