Solving the Weighted Parity Problem for Gammoids by Reduction to Graphic Matching
Po Tong and Eugene L. Lawler and V. V. Vazirani
EECS Department, University of California, Berkeley
Technical Report No. UCB/CSD-82-103
, 1982
http://www2.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}, Year= {1982}, Month= {Apr}, Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/6203.html %F Tong:CSD-82-103