کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9657811 690106 2005 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The approximability of the weighted Hamiltonian path completion problem on a tree
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The approximability of the weighted Hamiltonian path completion problem on a tree
چکیده انگلیسی
Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is observed that this problem is strongly NP-hard, so it does not have any fully polynomial-time approximation scheme (FPTAS) unless NP=P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 341, Issues 1–3, 5 September 2005, Pages 385-397
نویسندگان
, , ,