Name
Title | ||
|---|---|---|
Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph |
Abstract | ||
|---|---|---|
In this paper we present two new polynomial algorithms for the asymmetric version of the m -Peripatetic Salesman Problem ( m -APSP) which consists in finding m edge-disjoint Hamiltonian circuits of extremal total weight in a complete weighted digraph. The first algorithm solves the asymmetric 2-PSP on maximum. Its approximation ratio is equal to 2/3. The second algorithm deals with the minimization version of the asymmetric m-PSP on random instances. For this algorithm conditions for asymptotically exactness are presented. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.dam.2015.03.007 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Asymmetric m-Peripatetic Salesman Problem,Polynomial algorithm,Performance guarantees,Disjoint Hamiltonian circuits,Random inputs,Asymptotic optimality | Journal | 196 |
Issue | ISSN | Citations |
C | 0166-218X | 1 |
PageRank | References | Authors |
0.48 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| E. Kh. Gimadi | 1 | 1 | 1.83 |
| Alexei N. Glebov | 2 | 1 | 0.48 |
| A. A. Skretneva | 3 | 1 | 0.48 |
| O. Yu. Tsidulko | 4 | 1 | 2.85 |
| D. Zh. Zambalaeva | 5 | 1 | 0.48 |