Subcubic equivalences between path, matrix, and triangle problems
© 2018 ACM. We say an algorithm on n × n matrices with integer entries in [-M,M] (or n-node graphs with edge weights from [-M,M]) is truly subcubic if it runs in O(n3 - δ · poly(log M)) time for some δ > 0. We define a notion of subcubic reducibility and show that many important problems on graph...
| Main Authors: | , |
|---|---|
| 其他作者: | |
| 格式: | Article |
| 語言: | English |
| 出版: |
2021
|
| 在線閱讀: | https://hdl.handle.net/1721.1/134750 |