25 citations · 78 across the 46 of their papers we have counts for
4 papers · 1 filter
A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts
Tung Mai, Vijay V. Vazirani
We study a natural generalization of stable matching to the maximum weight stable matching problem and we obtain a combinatorial polynomial time algorithm for it by reducing it to…
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications
Rohith Reddy Gangam, Tung Mai, Nitya Raju +1
Recently MV18 identified and initiated work on the new problem of understanding structural relationships between the lattices of solutions of two "nearby" instances of stable match…
Finding Stable Matchings that are Robust to Errors in the Input
Tung Mai, Vijay V. Vazirani
We study the problem of finding solutions to the stable matching problem that are robust to errors in the input and we obtain a polynomial time algorithm for a special class of err…
NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
David Eppstein, Vijay V. Vazirani
In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in -minor-free graphs by building on Kasteleyn's scheme for planar graphs, and stated…