کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646518 | 1632249 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A linear time algorithm to compute square of interval graphs and their colouring
ترجمه فارسی عنوان
یک الگوریتم زمان خطی برای محاسبه مربع نمودارهای فاصله ای و رنگ آمیزی آنها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار فاصله ای؛ مربع نمودار. دسته؛ برچسب زنی L (1،1) L (1،1)
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The square of a graph G=(V,E)G=(V,E), denoted by G2G2, is a graph on the same vertex set V(G)V(G) such that two vertices xx and yy are adjacent in G2G2 if and only if there is a path of length one or two between xx and yy in GG. In this article, a new linear time algorithm is presented to compute G2G2 from GG when GG is an interval graph. Also a linear time algorithm is designed to find all the maximal cliques of G2G2 from GG. Application of square of interval graphs in the field of L(h,k)L(h,k)-labelling problem is also discussed. Finally, it is shown that L(1,1)L(1,1)-labelling number of an interval graph can be computed in linear time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 13, Issue 1, April 2016, Pages 54–64
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 13, Issue 1, April 2016, Pages 54–64
نویسندگان
Satyabrata Paul, Madhumangal Pal, Anita Pal,