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" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.