2 Strong Components (dynamic) (Strongly Connected Components)
Revision as of 11:19, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2 Strong Components (dynamic) (Strongly Connected Components)}} == Description == maintain: a directed graph, under: edge insertion/deletions, answer: are there more than 2 strongly connected components? == Related Problems == Related: Strongly Connected Components, Transitive Closure, Maximum Strongly Connected Component, Strong Connectivity (dynamic), Connected Subgraph == Parameters == No parameters found. == Table of Algori...")
Description
maintain: a directed graph, under: edge insertion/deletions, answer: are there more than 2 strongly connected components?
Related Problems
Related: Strongly Connected Components, Transitive Closure, Maximum Strongly Connected Component, Strong Connectivity (dynamic), Connected Subgraph
Parameters
No parameters found.
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| CNF-SAT | if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing then: SETH is false |
2014 | https://ieeexplore.ieee.org/abstract/document/6979028?casa_token=daaoBjrHUa4AAAAA:DCjk_WMWZ5Is6KvGpmS8a2bL9LskvV0P1zEG4U2u-Tm_C8sixu1w65OpTyjml1HEpaikXhtYsg | link |