Approximation algorithm for maximum edge coloring

作者：Feng Wangsen^*; Zhang Li'ang; Wang Hanpin

来源：Theoretical Computer Science, 2009, 410(11): 1022-1029.

DOI：10.1016/j.tcs.2008.10.035

• Maximum edge coloring
• Approximation algorithm
• Wireless mesh networks

We propose a polynomial time approximation algorithm for a novel maximum edge coloring problem which arises from wireless mesh networks [Ashish Raniwala, Tzi-cker Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, in: INFOCOM 2005, pp. 2223-2234; Ashish Raniwala, Kartik Gopalan, Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, Mobile Comput. Commun. Rev. 8 (2) (2004) 50-65]. The problem is to color all the edges in a graph with maximum number of colors under the following q-Constraint: for every vertex in the graph, all the edges incident to it are colored with no more than q (q is an element of Z, q >= 2) colors. We show that the algorithm is a 2-approximation for the case q = 2 and a (1 4q-2/3q(2)-5q 2)-approximation for the case q > 2 respectively. The case q = 2 is of great importance in practice. For complete graphs and trees, polynomial time accurate algorithms are found for them when q = 2. The approximation algorithm gives a feasible solution to channel assignment in multi-channel wireless mesh networks.

• 出版日期2009-3-6
• 单位北京大学