Given a weighted planar bipartite graph G(A ∪ B, E) where each edge has an integer edge cost, we give an Õ(n4/3log nC) time algorithm to compute minimum-cost perfect matching; here C is the maximum edge cost in the graph. The previous best-known planarity exploiting algorithm has a running time of O(n3/2log n) and is achieved by using planar separators (Lipton and Tarjan ’80). Our algorithm is based on the bit-scaling paradigm (Gabow and Tarjan ’89). For each scale, our algorithm first executes O(n1/3) iterations of Gabow and Tarjan’s algorithm in O(n4/3) time leaving only O(n2/3) vertices unmatched. Next, it constructs a compressed residual graph H with O(n2/3) vertices and O(n) edges. This is achieved by using an r-division of the planar graph G with r = n2/3. For each partition of the r-division, there is an edge between two vertices of H if and only if they are connected by a directed path inside the partition. Using existing efficient shortest-path data structures, the remaining O(n2/3) vertices are matched by iteratively computing a minimum-cost augmenting path, each taking Õ(n2/3) time. Augmentation changes the residual graph, so the algorithm updates the compressed representation for each partition affected by the change in Õ(n2/3) time. We bound the total number of affected partitions over all the augmenting paths by O(n2/3 log n). Therefore, the total time taken by the algorithm is Õ(n4/3). [ABSTRACT FROM AUTHOR]
Copyright of ACM Transactions on Algorithms is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
