کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6421883 | 1631834 | 2013 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A lower bound on the Hamiltonian path completion number of a line graph
ترجمه فارسی عنوان
حد پایین تر از شماره تکمیل مسیر همیلتون در یک گراف خط
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شماره تکمیل مسیر همیلتون نمودار خط، غرور دنباله، کران پایین،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
چکیده انگلیسی
Given a line graph L(G) of a graph G=(V,E), the problem of finding the minimum number of edges to add to L(G) to have a Hamiltonian path on L(G) is considered. This problem, related to different applications, is known to be NP-hard. This paper presents an O(|V|+|E|) algorithm to determine a lower bound for the Hamiltonian path completion number of a line graph. The algorithm is based on finding a collection of edge-disjoint trails dominating all the edges of the root graph G. The algorithm is tested by an extensive experimental study showing good performance suggesting its use as a building block of exact as well as heuristic solution approaches for the problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 220, 1 September 2013, Pages 296-304
Journal: Applied Mathematics and Computation - Volume 220, 1 September 2013, Pages 296-304
نویسندگان
Paolo Detti, Carlo Meloni, Marco Pranzo,