Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952441 | Theoretical Computer Science | 2016 | 11 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xingchao Deng, Hengzhe Li, Guiying Yan,