On common edges in optimal solutions to traveling salesman and other optimization problems
type: Item
instance of: scholarly article
title: On common edges in optimal solutions to traveling salesman and other optimization problems
zbMATH Open document ID: 0648.90082
DOI: 10.1016/0166-218X(88)90057-1
author: S. H. Smith
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: Relationships between the symmetric traveling salesman problem (TSP), the minimum perfect matching problem (MPM) and the minimum spanning tree problem (MST), defined on a complete graph with n vertices where a cost is given for each edge, are explored. The main result shows that: if n is even, there exist optimal solutions to TSP and MPM which have at least two common edges; there exist optimal solutions to TSP and MST which have at least two common edges; and if n is even, there exist optimal solutions to MPM and MST which have at least one common edge. Problem instances are presented to demonstrate that these lower bounds on the number of common edges can be attained, thus proving that no stronger result is possible.
reviewed by: C.N.Potts
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 4059144
zbMATH Keywords: symmetric traveling salesman
zbMATH Keywords: minimum perfect matching
zbMATH Keywords: minimum spanning tree
zbMATH Keywords: complete graph
zbMATH Keywords: common edges
MaRDI profile type: Publication
cites work: A census of maximum uniquely hamiltonian graphs
cites work: Parity results on connected f-factors
cites work: Q3941433
cites work: Q3852212
cites work: Parity theorems for paths and cycles in graphs
cites work: Spanning cycles of nearly cubic graphs
cites work: Q4198056
cites work: The traveling-salesman problem and minimum spanning trees: Part II
cites work: Q4130999
cites work: Q5187226
cites work: Q3959443
cites work: Graphs with exactly one hamiltonian circuit
cites work: Q3707420
cites work: Hamiltonian Cycles and Uniquely Edge Colourable Graphs
description: scientific article; zbMATH DE number 4059144