کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952441 | 1442034 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithm on rainbow connection for maximal outerplanar graphs
ترجمه فارسی عنوان
الگوریتم اتصال رنگین کمان برای نمودار های بیرونی فلانار حداکثر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 651, 25 October 2016, Pages 76-86
Journal: Theoretical Computer Science - Volume 651, 25 October 2016, Pages 76-86
نویسندگان
Xingchao Deng, Hengzhe Li, Guiying Yan,