A bound for the symmetric travelling salesman problem through matroid formulation

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

Peter I. Cowling, Francesco Maffioli

Publication date: 27 January 1999

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

zbMATH Keywords

bound; matroid; symmetric traveling salesman

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05B35: Combinatorial aspects of matroids and geometric lattices

Related Items

The cardinality constrained covering traveling salesman problem

Uses Software

• TSPLIB

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item