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

DOI10.1016/0377-2217(86)90217-1zbMATH Open0583.90100OpenAlexW2019292134MaRDI QIDQ1069451FDOQ1069451

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

circuitstraveling salesmancomputational resultsill-conditioned1-tree relaxationedge eliminationshortest complete cycle problem

Mathematics Subject Classification ID

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

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
• On the Relation Between the Traveling-Salesman and the Longest-Path Problems
• Computer Solutions of the Traveling Salesman Problem
• Distance conserving reductions for nonoriented networks
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• Identification of non-optimal arcs for the traveling salesman problem

Cited In (2)

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

   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 👍 👎

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)