UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-82-103.pdf
Oskicat catalog record
Conditions of Use

Archive Home Page

Solving the Weighted Parity Problem for Gammoids by Reduction to Graphic Matching

Authors:
Tong, Po
Lawler, E.L.
Vazirani, V. V.
Technical Report Identifier: CSD-82-103
April 21, 1982
CSD-82-103.pdf

Abstract: It is shown that the weighted parity problem for gammoids, with matching and transversal matroids as special cases, can be reduced to the weighted graphic matching problem. Since the cycle matroid of a series parallel graph is a gammoid, this means that it is possible to solve the weighted parity problem for the cycle matroid of a series parallel graph by graphic matching.