Loading...
Please wait, while we are loading the content...
Similar Documents
Linear and o(n log n) time minimum-cost matching algorithms for quasi-convex tours (2001).
| Content Provider | CiteSeerX |
|---|---|
| Author | Buss, Samuel R. Yianilos, Peter N. |
| Abstract | Let G be a complete, weighted, undirected, bipartite graph with n red nodes, n ′ blue nodes, and symmetric cost function c(x, y). A maximum matching for G consists of min{n, n ′ } edges from distinct red nodes to distinct blue nodes. Our objective is to find a minimumcost maximum matching, i.e., one for which the sum of the edge costs has minimal value. This is the weighted bipartite matching problem; or as it is sometimes called, the assignment problem. We report a new and very fast algorithm for an abstract special case of this problem. Our first requirement is that the nodes of the graph are given as a ‘quasi-convex tour’. This means that they are provided circularly ordered as x1,...,xN where N = n + n ′,and that for any xi,xj,xk,xℓ, not necessarily adjacent but in tour order, with xi,xj of one color and xk,xℓ of the opposite color, the following inequality holds: |
| File Format | |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Subject Keyword | Quasi-convex Tour Time Minimum-cost Matching Algorithm Blue Node Symmetric Cost Function Minimumcost Maximum Matching Red Node Abstract Special Case Following Inequality Tour Order Distinct Red Node Weighted Bipartite Matching Problem Minimal Value Assignment Problem Opposite Color Bipartite Graph First Requirement Maximum Matching |
| Content Type | Text |
