Tuesday, 15:15 - 15:40 h, Room: H 3005


Ho Yee Cheung
Algebraic algorithms for linear matroid parity problems

Coauthors: Lap Chi Lau, Kai Man Leung


We present faster and simpler algebraic algorithms for the linear matroid parity
problem and its applications. For the linear matroid parity problem, we obtain
a simple randomized algorithm with running time O(mrω-1), which
improves the O(mrω)-time algorithm by Gabow and Stallmann. We also
present a very simple alternative algorithm with running time O(mr2).
We further improve the algebraic algorithms for some specific graph problems
of interest.
We present faster randomized algorithms for the Mader's disjoint S-path
problem and the graphic matroid parity problem.
The techniques are based on the algebraic algorithmic framework developed by
Mucha, Sankowski and Harvey.
While linear matroid parity and Mader's disjoint S-path
are challenging generalizations for the design of combinatorial algorithms,
our results show that both the algebraic algorithms for linear
matroid intersection and graph matching can be extended nicely to
more general settings.
All algorithms are still faster than the existing algorithms even if fast matrix
multiplications are not used.
These provide simple algorithms that can be easily implemented.


Talk 1 of the invited session Tue.3.H 3005
"Matroid parity" [...]
Cluster 2
"Combinatorial optimization" [...]


  Illinois Payday Loans should not be obtained by people who do not have the capacity to repay the lenders. The main advantage of Viagra Soft Tablets comparing with other products of this type is its faster on-set effect.