کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420313 | 683921 | 2006 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Hamiltonian problem on distance-hereditary graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper, we first present an O(n+m)O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G , respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n2)O(n2) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn)O(logn) time using O((n+m)/logn)O((n+m)/logn) processors on an EREW PRAM.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 3, 1 March 2006, Pages 508–524
Journal: Discrete Applied Mathematics - Volume 154, Issue 3, 1 March 2006, Pages 508–524
نویسندگان
Sun-Yuan Hsieh, Chin-Wen Ho, Tsan-Sheng Hsu, Ming-Tat Ko,