Research.
My research is in the design and analysis of algorithms (especially
graph algorithms), combinatorial optimization and linear programming.
Most recent papers
The first part of this article presents a data structure for weighted
matching in time
O(n(m+n log n)).
Then we extend this to arbitrary
degree constraints. (This entails
first defining
blossoms, and then giving simple algorithms
for maximum weight b-matchings and f-factors.)
The weighted matching approach to maximum cardinality matching,
18 pages.
A complete algorithm for nonbipartite matching
in time O(
√nm).
Appendix shows the approach can give a simple
correctness proof
for the
Micali-Vazirani matching algorithm.
Also includes a detailed correctness proof of the DFS alternative
to the MV DDFS algorithm.
This article presents a data structure used in the above weighted
matching algorithm.