A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem Full article
| Journal |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||
|---|---|---|---|
| Output data | Year: 2020, Volume: 1275, Pages: 3-15 Pages count : 13 DOI: 10.1007/978-3-030-58657-7_1 | ||
| Tags | Approximation algorithm; Clustering problem; Edge-colored graph; Linear relaxation; Worst-case analysis | ||
| Authors |
|
||
| Affiliations |
|
Abstract:
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].
Cite:
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
Identifiers:
| Scopus: | 2-s2.0-85092076438 |
| OpenAlex: | W3086307499 |