標題: The approximability of the weighted Hamiltonian path completion problem on a tree
作者: Wu, Q
Lu, CL
Lee, RCT
生物科技學系
Department of Biological Science and Technology
關鍵字: Hamiltonian path completion problem;trees;strongly NP-hard;approximation algorithm;fully polynomial-time approximation scheme
公開日期: 5-九月-2005
摘要: 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. (c) 2005 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.tcs.2005.03.043
http://hdl.handle.net/11536/13277
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2005.03.043
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 341
Issue: 1-3
起始頁: 385
結束頁: 397
顯示於類別:期刊論文


文件中的檔案:

  1. 000231660900020.pdf