Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.tcs.2005.03.043 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
augmenting edge,constant ratio approximation algorithm,edge weight,Hamiltonian path completion problem,augmented graph,polynomial-time approximation scheme,weighted Hamiltonian path completion,approximation algorithm,Hamiltonian path,performance ratio | Journal | 341 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 2 |
PageRank | References | Authors |
0.41 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Quincy Wu | 1 | 27 | 6.33 |
| Chin Lung Lu | 2 | 423 | 34.59 |
| Richard Chia-Tung Lee | 3 | 42 | 2.90 |