A note on finding a shortest complete cycle in an undirected graph
type: Item
instance of: scholarly article
title: A note on finding a shortest complete cycle in an undirected graph
zbMATH Open document ID: 0583.90100
DOI: 10.1016/0377-2217(86)90217-1
author: A. Volgenant
author: G. A. P. Kindervater
author: Roy Jonker
published in: European Journal of Operational Research
publication date: 1986-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3934805
zbMATH Keywords: circuits
zbMATH Keywords: edge elimination
zbMATH Keywords: shortest complete cycle problem
zbMATH Keywords: traveling salesman
zbMATH Keywords: ill-conditioned
zbMATH Keywords: 1-tree relaxation
zbMATH Keywords: computational results
MaRDI profile type: Publication
full work available at URL: 0377-2217(86)90217-1
OpenAlex ID: W2019292134
cites work: A cutting plane procedure for the travelling salesman problem on road networks
cites work: Distance conserving reductions for nonoriented networks
cites work: On the Relation Between the Traveling-Salesman and the Longest-Path Problems
cites work: Identification of non-optimal arcs for the traveling salesman problem
cites work: Nonoptimal Edges for the Symmetric Traveling Salesman Problem
cites work: Computer Solutions of the Traveling Salesman Problem
cites work: Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
cites work: The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
Recommended article: A note on cycle lengths in graphs
Recommended article: Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
Recommended article: Efficient approximation algorithms for shortest cycles in undirected graphs
Recommended article: A note on short cycles in digraphs
Recommended article: Finding a shortest cycle in a subspace of the cycle space of a graph
Recommended article: Finding short cycles in embedded graph in polynomial time
Recommended article: Problem statements for \(k\)-node shortest path and \(k\)-node shortest cycle in a complete graph
Recommended article: A note on graphs without short even cycles
Recommended article: A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
Recommended article: Shortest coverings of graphs with cycles
description: scientific article; zbMATH DE number 3934805