Approximating Maximum Edge Coloring in Multigraphs
Approximating Maximum Edge Coloring in Multigraphs
复制标题
DOI：
10.1007/3-540-45753-4_11
复制
发表时间：
2002-09
影响因子：
9.4
通讯作者：
U. Feige;E. Ofek;Udi Wieder
中科院分区：
文献类型：
--
作者：
U. Feige;E. Ofek;Udi Wieder
本文研究了以下问题的复杂性，我们称之为最大边t-染色：给定一个多重图G和一个参数t，用t颜色给尽可能多的边着色，使得相邻的边都不着色为相同的颜色.（等价地，找出G的最大边诱导子图，它的色指数至多为t）。我们证明了对每个固定的t ≥ 2，存在某个∈ > 0，使得在优于1-∈的比率内逼近最大边t-着色是NP-困难的。我们设计了常数因子逼近比问题的逼近算法。我们的算法的一个有趣的功能是，它们允许我们估计的最佳解决方案的值，往往1 astgrows的乘法因子。我们的研究是出于在基于卫星的电信网络的呼叫准入问题。
We study the complexity of the following problem that we callMax edge t-coloring: given a multigraphGand a parametert, color as many edges as possible usingtcolors, such that no two adjacent edges are colored with the same color. (Equivalently, find the largest edge induced subgraph ofGthat has chromatic index at mostt). We show that for every fixedt≥ 2 there is some ∈ > 0 such that it is NP-hard to approximateMax edge t-coloringwithin a ratio better than 1-∈. We design approximation algorithms for the problem with constant factor approximation ratios. An interesting feature of our algorithms is that they allow us to estimate the value of the optimum solution up to a multiplicative factor that tends to 1 astgrows. Our study was motivated by call admittance issues in satellite based telecommunication networks.