Average-case complexity of the min-sum matrix product problem
From MaRDI portal
Publication:897863
DOI10.1016/j.tcs.2015.09.008zbMath1331.68105OpenAlexW1505363495MaRDI QIDQ897863
Hongyu Liang, Ken C. K. Fong, Hao Yuan, Linji Yang, Minming Li
Publication date: 8 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.09.008
Analysis of algorithms and problem complexity (68Q25) Numerical computation of matrix norms, conditioning, scaling (65F35)
Cites Work
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- Time bounds for selection
- All-pairs shortest paths and the essential subgraph
- Gaussian elimination is not optimal
- Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication
- An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
- An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
- New Bounds on the Complexity of the Shortest Path Problem
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- Order Statistics
- Faster all-pairs shortest paths via circuit complexity
- A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
