Reduction from OuMv to Bipartite Graph MCM
Revision as of 12:19, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: OuMv TO: Bipartite Graph MCM == Description == == Implications == assume: OMv<br/>then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to d...")
FROM: OuMv TO: Bipartite Graph MCM
Description
Implications
assume: OMv
then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$
Year
2016
Reference
Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to diameter. arXiv preprint arXiv:1602.06705.