Browse Prior Art Database

Solution of Weighted 2-Matchings for Solving the Traveling Salesman Problem

IP.com Disclosure Number: IPCOM000035196D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28

Publishing Venue

IBM

Related People

Authors:
Stone, HS [+details]

Abstract

This article describes a new algorithm for finding a minimum-cost weighted 2-matching. The algorithm solves the bipartite weighted 2- matching problem in a context in which it can be used for a solution to the traveling salesman problem. The bipartite weighted 2-matching problem is a problem in which there is a bipartite graph with N source nodes, N sink nodes, and edges (i, j) where i is a source node and j is a sink node. Each edge carries a weight wt(i, j). The objective is to find a maximal 2-matching of minimum weight. A 2-matching is a subset of edges with the property that no sink or source node touches more than two edges in the matching. A maximal matching is a matching that contains as many edges as possible.