QQ客服 官方微博 反馈留言

	Approximation algorithms for maximum edge coloring problem
	Feng, Wangsen ; Zhang, Li&apos ; Qu, Wanling ; Wang, Hanpin ; ang
	2007
关键词	NETWORK
英文摘要	We propose polynomial time approximation algorithms for a novel maximum edge coloring problem which arises from the field of wireless mesh networks [8]. The problem is about coloring all the edges in a graph and finding a coloring solution which uses the maximum number of colors with the 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. The case q = 2 is of great importance in practice. In this paper, we design approximation algorithms for cases q = 2 and q > 2 with approximation ratio 2.5 and 1 + 4q-2/3q(2) - 5q+2 respectively. The algorithms can give practically usable estimations on the upper bounds of the numbers of the channels used in wireless mesh networks.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000246671900059&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Theory & Methods; CPCI-S(ISTP); 2
语种	英语
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/293370]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Feng, Wangsen,Zhang, Li&apos,Qu, Wanling,et al. Approximation algorithms for maximum edge coloring problem. 2007-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。