Algorithm on rainbow connection for maximal outerplanar graphs

详细信息    查看全文

• 作者：Xingchao Deng^a ; ^{xcdeng@mail.tjnu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; ^{dengyuqiu1980@126.com" class="auth_mail" title="E-mail the corresponding author} ; Hengzhe Li^b ; Guiying Yan^c
• 关键词：Rainbow connection number ; Maximal outerplanar graph ; Diameter ; Algorithm
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：25 October 2016
• 年：2016
• 卷：651
• 期：Complete
• 页码：76-86
• 全文大小：510 K

文摘

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)$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$2rad(G)+2+c,0\le c\le rad(G)-2$ colors in polynomial time.