Reduction from CNF-SAT to dynamic st-Maximum Flow
Revision as of 12:19, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: dynamic st-Maximum Flow == Description == == Implications == assume: SETH<br/>then: there is no algorithm for solving incremental (or decremental) st-max-flow on a weighted and directed graph with $n$ nodes and $\tilde{O}(n)$ edges with amortized time $O(m^{1-\epsilon})$ per operation for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to...")
FROM: CNF-SAT TO: dynamic st-Maximum Flow
Description
Implications
assume: SETH
then: there is no algorithm for solving incremental (or decremental) st-max-flow on a weighted and directed graph with $n$ nodes and $\tilde{O}(n)$ edges with amortized time $O(m^{1-\epsilon})$ per operation 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.