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

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)

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

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)