Algorithm on rainbow connection for maximal outerplanar graphs

doi:10.1016/j.tcs.2016.08.020

CSpace > 应用数学研究所

	Algorithm on rainbow connection for maximal outerplanar graphs
	Deng, Xingchao 1; Li, Hengzhe 2; Yan, Guiying3
	2016-10-25
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	651 页码:76-86
摘要	In this paper, we consider rainbow connection number of maximal outerplanar graphs (MOPS) on algorithmic aspect. For the (MOP) G, we give sufficient conditions to guarantee that rc(G) = diam(G). Moreover, we produce the graph with given diameter D and give their rainbow coloring in linear time. X. Deng et al. [4] give a polynomial time algorithm to compute the rainbow connection number of MOPS by the Maximal fan partition method, but only obtain a compact upper bound. J. Lauri [11] proved that, for chordal outerplanar graphs given an edge-coloring, to verify whether it is rainbow connected is NP-complete under the coloring, it is so for MOPs. Therefore we construct Central-cut spine of MOP G, by which we design an algorithm to give a rainbow edge coloring with at most 2rad(G) + 2 + c, 0 <= c <= rad(G) - 2 colors in polynomial time. (C) 2016 Elsevier B.V. All rights reserved.
关键词	Rainbow connection number Maximal outerplanar graph Diameter Algorithm
DOI	10.1016/j.tcs.2016.08.020
语种	英语
资助项目	National Natural Science Foundation of China[11401181] ; Tian Jin Normal University Project[52XB1206]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000386417600006
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/23877
专题	应用数学研究所
通讯作者	Deng, Xingchao
作者单位	1.Tianjin Normal Univ, Coll Math, Tianjin 300071, Peoples R China 2.Henan Normal Univ, Coll Math & Informat Sci, Xinxiang 453007, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Deng, Xingchao,Li, Hengzhe,Yan, Guiying. Algorithm on rainbow connection for maximal outerplanar graphs[J]. THEORETICAL COMPUTER SCIENCE,2016,651:76-86.
APA	Deng, Xingchao,Li, Hengzhe,&Yan, Guiying.(2016).Algorithm on rainbow connection for maximal outerplanar graphs.THEORETICAL COMPUTER SCIENCE,651,76-86.
MLA	Deng, Xingchao,et al."Algorithm on rainbow connection for maximal outerplanar graphs".THEORETICAL COMPUTER SCIENCE 651(2016):76-86.