Bounded Max-colorings of Graphs

被引：0

作者：

Bampis, Evripidis ^{[1
]}

Kononov, Alexander ^{[2
]}

Lucarelli, Giorgio ^{[3
]}

Milis, Ioannis ^{[4
]}

机构：

[1] Univ Paris 06, LIP6, F-75252 Paris 05, France

[2] Sobolev Inst Mat, Novosibirsk, Russia

[3] Univ Paris 09, CNRS, LAMSADE, FRE 3234, Paris, France

[4] Univ Econm & Business, Athens, Greece

来源：

ALGORITHMS AND COMPUTATION, PT I | 2010年 / 6506卷

关键词：

COMPLEXITY; NUMBER;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most b and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes' weights. These problems generalize the well known max-coloring problems by taking into account the number of available resources (colors) in practical applications. In this paper we present complexity results and approximation algorithms for the bounded max-coloring problems on general graphs, bipartite graphs and trees.

引用

页码：353 / +

页数：3

共 22 条

[1] A NOTE ON THE DECOMPOSITION OF GRAPHS INTO ISOMORPHIC MATCHINGS [J].