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

DOI10.1016/0377-2217(86)90217-1MaRDI QIDQ1069451zbMATH OpenOpenAlexFDO

Authors 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

1-tree relaxationcircuitscomputational resultsedge eliminationill-conditionedshortest complete cycle problemtraveling salesman

Mathematics Subject Classification ID

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

Review text

How to transform a shortest complete cycle problem into a traveling salesman problem is well known. Although these problems appear ill- conditioned, a 1-tree relaxation based traveling salesman algorithm solves them rather easily (up to 150 nodes), provided non-optimal edges are eliminated. The computational results are considerably better than known results for a linear programming approach.

Recommendations

• A note on cycle lengths in graphs
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Efficient approximation algorithms for shortest cycles in undirected graphs
• A note on short cycles in digraphs
• Finding a shortest cycle in a subspace of the cycle space of a graph
• Finding short cycles in embedded graph in polynomial time
• Problem statements for k-node shortest path and k-node shortest cycle in a complete graph
• A note on graphs without short even cycles
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Shortest coverings of graphs with cycles

Cites work

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

Cited in

(4)

• A new class of cutting planes for the symmetric travelling salesman problem
• Problem statements for k-node shortest path and k-node shortest cycle in a complete graph
• scientific article; zbMATH DE number 3847427 (Why is no real title available?)
• A new integer programming formulation of the graphical traveling salesman problem

This page was built for publication: A note on finding a shortest complete cycle in an undirected graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069451)