A bound for the symmetric travelling salesman problem through matroid formulation

DOI10.1016/0377-2217(95)00008-EzbMath0904.90166OpenAlexW2043617956MaRDI QIDQ1388823

Francesco Maffioli, Peter I. Cowling

Publication date: 27 January 1999

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

Full work available at URL: https://doi.org/10.1016/0377-2217(95)00008-e

zbMATH Keywords

boundmatroidsymmetric traveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (1)

The cardinality constrained covering traveling salesman problem

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Two algorithms for weighted matroid intersection
• Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
• Intersection of Two Matroids: (Condensed) Border Graphs and Ranking
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• A weighted matroid intersection algorithm
• TSPLIB—A Traveling Salesman Problem Library
• A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
• The traveling-salesman problem and minimum spanning trees: Part II

This page was built for publication: A bound for the symmetric travelling salesman problem through matroid formulation