A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem Научная публикация
| Журнал |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||
|---|---|---|---|
| Вых. Данные | Год: 2020, Том: 1275, Страницы: 3-15 Страниц : 13 DOI: 10.1007/978-3-030-58657-7_1 | ||
| Ключевые слова | Approximation algorithm; Clustering problem; Edge-colored graph; Linear relaxation; Worst-case analysis | ||
| Авторы |
|
||
| Организации |
|
Реферат:
In the Max k-Edge-Colored Clustering problem (abbreviated as MAX-k-EC) we are given an undirected graph and k colors. Each edge of the graph has a color and a nonnegative weight. The goal is to color the vertices so as to maximize the total weight of the edges whose colors coincide with the colors of their endpoints. The problem was introduced by Angel et al. [3]. In this paper we give a polynomial-time algorithm for MAX-k-EC with an approximation factor which significantly improves the best previously known approximation bound established by Alhamdan and Kononov [2].
Библиографическая ссылка:
Ageev A.A.
, Kononov A.V.
A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem
Communications in Computer and Information Science. 2020. V.1275. P.3-15. DOI: 10.1007/978-3-030-58657-7_1 Scopus OpenAlex
A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem
Communications in Computer and Information Science. 2020. V.1275. P.3-15. DOI: 10.1007/978-3-030-58657-7_1 Scopus OpenAlex
Идентификаторы БД:
| Scopus: | 2-s2.0-85092076438 |
| OpenAlex: | W3086307499 |