|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Clustering on k-Edge-Colored Graphs, Discrete Applied Mathematics, 2016. Vol 211. P. 15-22 DOI: 10.1016/j.dam.2016.04.017статья
- Авторы: Angel E., Bampis E., Kononov A., Paparas D., Pountourakis E., Zissimopoulos V.
- Журнал: Discrete Applied Mathematics
- Том: 211
- Год издания: 2016
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 15
- Последняя страница: 22
- DOI: 10.1016/j.dam.2016.04.017
- Аннотация: We study the Max k-colored clustering problem, where given an edge-colored graph withk colors, we seek to color the vertices of the graph so as to find a clustering of the verticesmaximizing the number (or the weight) of matched edges, i.e. the edges having the samecolor as their extremities. We show that the cardinality problem is NP-hard even for edge-colored bipartite graphs with a chromatic degree equal to two and k ≥ 3. Our main result is a constant approximation algorithm for the weighted version of the Max k-colored clustering problem which is based on a rounding of a natural linear programming relaxation. For graphs with chromatic degree equal to two we improve this ratio by exploiting the relation of our problem with the Max 2-and problem. We also present a reduction to the maximum weight independent set (IS) problem in bipartite graphs which leads to a polynomial time algorithm for the case of two colors.
- Добавил в систему: Кононов Александр Вениаминович