Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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