Approximating the maximum 2- and 3-edge-colorable subgraph problems
Approximating the maximum 2- and 3-edge-colorable subgraph problems
复制标题
近似最大 2 边和 3 边可着色子图问题
DOI：
10.1016/j.dam.2009.04.002
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Kosowski
中科院分区：
文献类型：
--
作者：
A. Kosowski
对于参数k≥2的固定值，最大k-边可着色子图问题是在一个简单图中找到k个边不相交的匹配，目标是最大化所使用的边的总数。已知该问题对于所有k都是APX困难的，但是存在多项式时间近似算法，随着k趋于无穷大，近似比趋于1。在这里，我们提出了改进的近似算法的情况下，k=2和k=3，具有5/6和4/5的近似比，分别。
For a fixed value of a parameter k≥2, the Maximum k-Edge-Colorable Subgraph Problem consists in finding k 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 k, but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as k tends to infinity. Herein we propose improved approximation algorithms for the cases of k=2 and k=3, having approximation ratios of 5/6 and 4/5, respectively.