On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight

DOI10.1007/s11590-015-0914-3zbMath1353.90171OpenAlexW832351726MaRDI QIDQ315484

Panayotis E. Nastou, Panos M. Pardalos, Vassilis Papadinas, Yannis C. Stamatiou

Publication date: 21 September 2016

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-015-0914-3

zbMATH Keywords

heuristicscombinatorial optimizationtravelling salesman problemminimum weight Hamiltonian cyclesnearest neighbor heuristic

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Euclidean traveling salesman problem is NP-complete
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• Nonlinear assignment problems. Algorithms and applications
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• P-Complete Approximation Problems
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Reducibility among Combinatorial Problems

This page was built for publication: On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight