Name
Title | ||
|---|---|---|
An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree |
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 shown that this problem will unlikely 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 |
|---|---|---|
2000 | 10.1007/3-540-40996-3_14 | ISAAC |
Keywords | Field | DocType |
approximate algorithm,augmenting edge,constant ratio approximation algorithm,edge weight,hamiltonian path completion problem,augmented graph,polynomial-time approximation scheme,approximation algorithm,hamiltonian path,performance ratio,weighted hamiltonian path completion,fully polynomial time approximation scheme | Approximation algorithm,Discrete mathematics,Graph,Combinatorics,Shortest path problem,Hamiltonian path,Algorithm,Combinatorial optimization,Hamiltonian path problem,Longest path problem,Mathematics,Widest path problem | Conference |
Volume | ISSN | ISBN |
1969 | 0302-9743 | 3-540-41255-7 |
Citations | PageRank | References |
2 | 0.37 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Q. S. Wu | 1 | 3 | 1.08 |
| Chin Lung Lu | 2 | 423 | 34.59 |
| Richard C. T. Lee | 3 | 123 | 29.25 |