Computer Science – Data Structures and Algorithms
Scientific paper
2006-01-09
Computer Science
Data Structures and Algorithms
Scientific paper
Basic path-matchings, introduced by Cunningham and Geelen (FOCS 1996), are a common generalization of matroid intersection and non-bipartite matching. The main results of this paper are a new algebraic characterization of basic path-matching problems and an algorithm for constructing basic path-matchings in O(n^w) time, where n is the number of vertices and w is the exponent for matrix multiplication. Our algorithms are randomized, and our approach assumes that the given matroids are linear and can be represented over the same field. Our main results have interesting consequences for several special cases of path-matching problems. For matroid intersection, we obtain an algorithm with running time O(nr^(w-1))=O(nr^1.38), where the matroids have n elements and rank r. This improves the long-standing bound of O(nr^1.62) due to Gabow and Xu (FOCS 1989). Also, we obtain a simple, purely algebraic algorithm for non-bipartite matching with running time O(n^w). This resolves the central open problem of Mucha and Sankowski (FOCS 2004).
No associations
LandOfFree
Algebraic Structures and Algorithms for Matching and Matroid Problems (Preliminary Version) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algebraic Structures and Algorithms for Matching and Matroid Problems (Preliminary Version), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic Structures and Algorithms for Matching and Matroid Problems (Preliminary Version) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-683653