Browse Prior Art Database

An Improvement to an Algorithm for Solving the Bipartite Weighted Matching

IP.com Disclosure Number: IPCOM000035192D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

This article describes an improvement to an algorithm for solving the bipartite weighted-matching problem. The bipartite weighted-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 matching of minimum weight. A matching is a subset of edges with the property that no sink or source node touches more than one edge in the matching. A maximal matching is a matching that contains as many edges as possible.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 38% of the total text.

Page 1 of 3

An Improvement to an Algorithm for Solving the Bipartite Weighted Matching

This article describes an improvement to an algorithm for solving the bipartite weighted-matching problem. The bipartite weighted-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 matching of minimum weight. A matching is a subset of edges with the property that no sink or source node touches more than one edge in the matching. A maximal matching is a matching that contains as many edges as possible.

The technique described here reduces the time to find a solution by a small constant factor. The worst-case time remains proportional to N3 where N is the number of items participating in the matching.

The underlying algorithm for the solution is described in [*]. The basic step is to find an augmenting path in a bipartite graph. An augmenting path is a shortest path along which a new edge can be added to the matching. How to find an augmenting path in O(N2) steps is shown in [*]. Since a maximal matching has N edges, the augmenting step has to be repeated N times. This gives an upper bound of N3 for the total effort. The Modification of Lawler's Algorithm

First we give a description of Lawler's algorithm. Then we describe how to create the linkages for the sink nodes that improve the running time of the algorithm.

The following definitions are required for the algorithm:

A source node is exposed if no arc in the present matching leaves that node.

A sink node is exposed if no arc in the present matching enters that node.

To find an augmenting path, it is necessary to find a path from an exposed source node to an exposed sink node that changes the present matching by the minimum possible weight. Such a path alternates between new edges not in the present matching and edges in the matching. It starts and ends with a new edge. Each new edge adds its weight to the matching. Each edge on the path that is in the present matching is removed from the next matching, so that the weights of these edges are deducted from the weight of the present matching when computing the weight of the next matching.

The search for an alternating path starts at set of nodes that are called reachable nodes as defined below. From the reachable nodes, the algorithm explores arcs that touch other nodes. In certain cases a node touched by one of these arcs becomes a member of the set of reachable nodes, and the search for an augmenting path continues from this node. Otherwise, a node touched in the search is unreachable, and a slack value is placed at the node to give a numerical measure of its unreachability.

1

Page 2 of 3

The key idea is the definition of reachable. A node n is reachable if there is an alternating path from some exposed source node to node n such that for every arc (i, j) on this path, vj -...