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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    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