Maximum matchings via Gaussian elimination
By Marcin Mucha, Piotr Sankowski. 45th Annual IEEE Symposium on Foundations of Computer Science, 2004
301 citations recorded by the source corpus.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/5eb5ede1a9d4d26ae3e0387036fa887835e0a799
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Moran Feldman
- Niv Buchbinder
- Amir Abboud
- Roy Schwartz
- Joseph (Seffi) Naor
- Virginia Vassilevska Williams
- Alex Kulesza
- B. Taskar
In Computer Networks and Communications
- Niv Buchbinder
- Amir Abboud
- Moran Feldman
- Virginia Vassilevska Williams
- Joseph (Seffi) Naor
- Roy Schwartz
- Aranyak Mehta
- Francis R. Bach
Citations in the corpus
- Submodular Maximization with Cardinality Constraints (2014, background): “Mucha and Sankowski [43] give such an algorithm whose expected time complexity is O(k), where ω is the exponent of matrix multiplication.”
- Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems (2014, methodology): “e matching problem has a long history. In a seminal paper, Hopcroft and Karp [52] designed an O(m √ n) time algorithm for the problem in bipartite graphs with m edges and n nodes. Mucha and Sankowski [67] (and Harvey [46]) improved their result for dense graphs by giving an O˜(nω)3 time algorithm wh”