Name
Abstract | ||
|---|---|---|
We consider the problem of computing a minimum-weight Hamiltonian cycle on an undirected graph with edges' weights from set {0,1,2}, where 0-weight edges create a perfect matching, of the graph. We provide a (4/3)-approximation algorithm and show that the problem it is APX-contplete. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1142/S0129054113500019 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Approximation algorithms, traveling salesman problem | Discrete mathematics,Strength of a graph,Combinatorics,Hypercube graph,Folded cube graph,Cycle graph,Mixed graph,Hamiltonian path problem,Hamiltonian completion,Factor-critical graph,Mathematics | Journal |
Volume | Issue | ISSN |
24 | 1 | 0129-0541 |
Citations | PageRank | References |
1 | 0.36 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Bienkowski | 1 | 254 | 27.18 |
| Pawel Zalewski | 2 | 1 | 0.36 |