Complexity of minimal tree routing and coloring

CSpace > 应用数学研究所

	Complexity of minimal tree routing and coloring
	Chen, XJ; Hu, XD; Jia, XH
	2005
发表期刊	ALGORITHMIC APPLICATIONS IN MANAGEMENT, PROCEEDINGS
ISSN	0302-9743
卷号	3521 页码:6-15
摘要	Let G be a undirected connected graph. Given a set of g groups each being a subset of V(G), tree routing and coloring is to produce g trees in G and assign a color to each of them in such a way that all vertices in every group are connected by one of produced trees and no two trees sharing a common edge are assigned the same color. In this paper we study how to find a tree routing and coloring that uses minimal number of colors, which finds an application of setting up multicast connections in optical networks. We first prove Omega(g(1-epsilon))-inapproximability of the problem even when G is a mesh, and then we propose some approximation algorithms with provable performance guarantees for general graphs and some special graphs as well.
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Interdisciplinary Applications ; Computer Science, Theory & Methods
WOS记录号	WOS:000230475100003
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/1307
专题	应用数学研究所
通讯作者	Chen, XJ
作者单位	1.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China 2.City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Chen, XJ,Hu, XD,Jia, XH. Complexity of minimal tree routing and coloring[J]. ALGORITHMIC APPLICATIONS IN MANAGEMENT, PROCEEDINGS,2005,3521:6-15.
APA	Chen, XJ,Hu, XD,&Jia, XH.(2005).Complexity of minimal tree routing and coloring.ALGORITHMIC APPLICATIONS IN MANAGEMENT, PROCEEDINGS,3521,6-15.
MLA	Chen, XJ,et al."Complexity of minimal tree routing and coloring".ALGORITHMIC APPLICATIONS IN MANAGEMENT, PROCEEDINGS 3521(2005):6-15.