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

### Po Tong, Eugene L. Lawler and V. V. Vazirani

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-82-103

April 1982

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1982/CSD-82-103.pdf

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.

BibTeX citation:

@techreport{Tong:CSD-82-103, Author = {Tong, Po and Lawler, Eugene L. and Vazirani, V. V.}, Title = {Solving the Weighted Parity Problem for Gammoids by Reduction to Graphic Matching}, Institution = {EECS Department, University of California, Berkeley}, Year = {1982}, Month = {Apr}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1982/6203.html}, Number = {UCB/CSD-82-103}, 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.} }

EndNote citation:

%0 Report %A Tong, Po %A Lawler, Eugene L. %A Vazirani, V. V. %T Solving the Weighted Parity Problem for Gammoids by Reduction to Graphic Matching %I EECS Department, University of California, Berkeley %D 1982 %@ UCB/CSD-82-103 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1982/6203.html %F Tong:CSD-82-103