Content deleted Content added
Citation bot (talk | contribs) Alter: journal, title, template type. Add: isbn, date, chapter-url, chapter, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Hilst | #UCB_toolbar |
fix ref |
||
Line 31:
=== Implications of conjectured hardness ===
The OMv conjecture implies lower bounds on the time needed to solve a large class of dynamic graph problems, including [[reachability]] and [[Connectivity (graph theory)|connectivity]], [[Shortest path problem|shortest path]], and subgraph detection. For many of these problems, the implied lower bounds have matching upper bounds.<ref name=":0" /> While some of these lower bounds also followed from previous conjectures (e.g., [[3SUM]]),<ref>{{
| last1 = Abboud | first1 = Amir
| last2 = Williams | first2 = Virginia Vassilevska | author2-link = Virginia Vassilevska Williams
| arxiv = 1402.0054
| contribution = Popular conjectures imply strong lower bounds for dynamic problems
| doi = 10.1109/FOCS.2014.53
| pages = 434–443
| publisher = IEEE Computer Society
| title = 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014
| year = 2014}}</ref> many of the lower bounds that follow from OMv are stronger or new.
Later work showed that the OMv conjecture implies lower bounds on the time needed for subgraph counting in [[Average-case complexity|average-case]] graphs.<ref name=":1">{{Cite journal |last1=Henzinger |first1=Monika |last2=Lincoln |first2=Andrea |last3=Saha|first3=Barna |title=The Complexity of Average-Case Dynamic Subgraph Counting |url=https://doi.org/10.1137/1.9781611977073.23 |journal=ACM-SIAM Symposium on Discrete Algorithms (SODA) |series=SODA '22 |date=2022 |pages=459–498 |doi=10.1137/1.9781611977073.23 |isbn=978-1-61197-707-3 }}</ref>
| |||