کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420461 | 683942 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finding the longest isometric cycle in a graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A cycle in a graph GG is isometric if the distance between two vertices in the cycle is equal to their distance in GG. Finding the longest isometric cycle of a graph is then a natural variant of the problem of finding a longest cycle. While most variants of the longest cycle problem are NP-complete, we show that quite surprisingly, one can find a longest isometric cycle in a graph in polynomial time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 12, 28 June 2009, Pages 2670–2674
Journal: Discrete Applied Mathematics - Volume 157, Issue 12, 28 June 2009, Pages 2670–2674
نویسندگان
Daniel Lokshtanov,