| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420480 | Discrete Applied Mathematics | 2009 | 8 Pages |
Abstract
For a fixed value of a parameter k≥2k≥2, the Maximum kk-Edge-Colorable Subgraph Problem consists in finding kk edge-disjoint matchings in a simple graph, with the goal of maximising the total number of edges used. The problem is known to be APX-hard for all kk, but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as kk tends to infinity. Herein we propose improved approximation algorithms for the cases of k=2k=2 and k=3k=3, having approximation ratios of 5/6 and 4/5, respectively.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Adrian Kosowski,