Loading...
Please wait, while we are loading the content...
Similar Documents
Solving the linear matroid parity problem as a sequence of matroid intersection problems (1990).
| Content Provider | CiteSeerX |
|---|---|
| Author | Orlin, James B. Vate, John H. Vande |
| Abstract | In this paper, we present an O(r 4 n) algorithm for the linear matroid parity problem. Our solution technique is to introduce a modest generalization, the non-simple parity problem, and identify an important subclass of non-simple parity problems called 'easy ' parity problems which can be solved as matroid intersection problems. We then show how to solve any linear matroid parity problem parametrically as a sequence of 'easy ' parity problems. In contrast to other algorithmic work on this problem, we focus on general structural properties of dual solutions rather than on local primal structures. In a companion paper, we develop these ideas into a duality theory for the parity problem. |
| File Format | |
| Publisher Date | 1990-01-01 |
| Access Restriction | Open |
| Subject Keyword | Linear Matroid Parity Problem Sequence Matroid Intersection Problem Parity Problem Non-simple Parity Problem Important Subclass Matroid Intersection Problem Companion Paper Solution Technique Dual Solution Local Primal Structure Algorithmic Work Modest Generalization General Structural Property Duality Theory |
| Content Type | Text |
