On common edges in optimal solutions to traveling salesman and other optimization problems (Q1105496)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On common edges in optimal solutions to traveling salesman and other optimization problems |
scientific article |
Statements
On common edges in optimal solutions to traveling salesman and other optimization problems (English)
0 references
1988
0 references
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.
0 references
symmetric traveling salesman
0 references
minimum perfect matching
0 references
minimum spanning tree
0 references
complete graph
0 references
common edges
0 references