A note on finding a shortest complete cycle in an undirected graph

DOI10.1016/0377-2217(86)90217-1zbMath0583.90100OpenAlexW2019292134MaRDI QIDQ1069451

A. Volgenant, G. A. P. Kindervater, Roy Jonker

Publication date: 1986

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(86)90217-1

zbMATH Keywords

traveling salesmancircuitscomputational resultsill-conditioned1-tree relaxationedge eliminationshortest complete cycle problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35)

Related Items

A new class of cutting planes for the symmetric travelling salesman problem, A new integer programming formulation of the graphical traveling salesman problem

Cites Work

• Distance conserving reductions for nonoriented networks
• A cutting plane procedure for the travelling salesman problem on road networks
• Identification of non-optimal arcs for the traveling salesman problem
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
• On the Relation Between the Traveling-Salesman and the Longest-Path Problems
• Computer Solutions of the Traveling Salesman Problem