کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419243 | 683758 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum strictly fundamental cycle bases of planar graphs are hard to find
ترجمه فارسی عنوان
حداقل هسته چرخه ای بنیادین گرافهای مسطح برای پیدا کردن سخت است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we consider the problem of finding a spanning tree in a graph that minimizes the sum over the lengths of the cycles induced by the chords of the tree. We show the NPNP-completeness of this problem for planar graphs. The proof will be by reduction of a planar version of the Exact Cover By 3-Sets Problem. Finding such a minimum strictly fundamental cycle basis has various practical applications, e.g. in designing optimal periodic timetables in public transport.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 150–159
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 150–159
نویسندگان
Alexander Reich,