Conference proceeding
Clustering on kEdge-Colored Graphs
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2013, Vol.8087, pp.50-61
Lecture Notes in Computer Science
01 Jan 2013
Abstract
We study the Max k-colored clustering problem, where, given an edge-colored graph with k colors, we seek to color the vertices of the graph so as to find a clustering of the vertices maximizing the number (or the weight) of matched edges, i.e. the edges having the same color 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.
Metrics
2 Record Views
Details
- Title
- Clustering on kEdge-Colored Graphs
- Creators
- Eric Angel - EvryEvripidis Bampis - Marie CurieAlexander Kononov - Sobolev Inst Math, Novosibirsk, RussiaDimitris Paparas - Columbia UniversityEmmanouil Pountourakis - Northwestern UniversityVassilis Zissimopoulos - National and Kapodistrian University of Athens
- Contributors
- K Chatterjee (Editor)J Sgall (Editor)
- Publication Details
- MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2013, Vol.8087, pp.50-61
- Series
- Lecture Notes in Computer Science
- Publisher
- Springer Nature
- Number of pages
- 12
- Grant note
- European Social Fund-ESF; European Social Fund (ESF) Greek national funds; Greek Ministry of Development-GSRT project ALGONOW of the research funding program THALIS 09-EMER-010 / ANR project TODO; Agence Nationale de la Recherche (ANR)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Identifiers
- 991021869108904721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
Source: InCites
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied