Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph

DOI10.1016/j.dam.2015.03.007zbMath1321.05101OpenAlexW2037601619MaRDI QIDQ499338

A. A. Skretneva, O. Yu. Tsidulko, D. Zh. Zambalaeva, Alekseĭ Nikolaevich Glebov, E. Kh. Gimadi

Publication date: 30 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.03.007

zbMATH Keywords

performance guaranteespolynomial algorithmasymptotic optimalityasymmetric \(m\)-peripatetic salesman problemdisjoint Hamiltonian circuitsrandom inputs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Signed and weighted graphs (05C22)

Related Items (2)

Safe and secure vehicle routing: a survey on minimization of risk exposure ⋮ An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• Better approximations for max TSP
• The traveling salesman problem and its variations
• A heuristic approach to the overnight security service problem
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Bounds for the symmetric 2-peripatetic salesman problem
• Well-solved cases of the 2-peripatetic salesman problem
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• Lower bounds for symmetricK-peripatetic salesman problems

This page was built for publication: Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph