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

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
نویسندگان
, , , ,