|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Bounded Max-colorings of Graphsтезисы доклада
- Авторы: Bampis E., Kononov A., Lucarelli G., Milis I.
- Сборник: Algorithms and Computation. ISAAC 2010
- Серия: Lecture Notes in Computer Science
- Том: 6506
- Тезисы
- Год издания: 2010
- Издательство: Springer Berlin
- Местоположение издательства: Heidelberg, Germany
- Первая страница: 353
- Последняя страница: 365
- DOI: 10.1007/978-3-642-17517-6_32
- Аннотация: 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.
- Добавил в систему: Кононов Александр Вениаминович