Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
From MaRDI portal
Publication:6051928
DOI10.1145/3563393OpenAlexW4296270819MaRDI QIDQ6051928
Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams
Publication date: 23 October 2023
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3563393
diametermedianradiusbetweenness centralityfine-grained complexityAPSPreach centralitysubcubic reductions
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths
- Matrix multiplication via arithmetic progressions
- Matching is as easy as matrix inversion
- Fast rectangular matrix multiplication and applications
- Which problems have strongly exponential complexity?
- A new approach to all-pairs shortest paths on real-weighted graphs
- On a class of \(O(n^ 2)\) problems in computational geometry
- Deterministic sublinear-time approximations for metric 1-median selection
- Experimental algorithms. 6th international workshop, WEA 2007, Rome, Italy, June 6--8, 2007. Proceedings.
- The centrality index of a graph
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A faster algorithm for betweenness centrality*
- Sublinear time algorithms for metric space problems
- Improved bound for complexity of matrix multiplication
- Towards polynomial lower bounds for dynamic problems
- Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Replacement paths and k simple shortest paths in unweighted directed graphs
- Faster Replacement Paths and Distance Sensitivity Oracles
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Approximating average parameters of graphs
- Faster Approximation of Distances in Graphs
- New Bounds on the Complexity of the Shortest Path Problem
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Faster All-Pairs Shortest Paths via Circuit Complexity
- New Bounds for Approximating Extremal Distances in Undirected Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- Fast Approximation of Centrality
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- Consequences of Faster Alignment of Sequences
- Fibonacci heaps and their uses in improved network optimization algorithms
- Reach for A*: Efficient Point-to-Point Shortest Path Algorithms
- Better Approximation of Betweenness Centrality
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Better Approximation Algorithms for the Graph Diameter
- Multiplying matrices faster than coppersmith-winograd
- Approximating Betweenness Centrality
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
- CENTRALITY ESTIMATION IN LARGE NETWORKS
This page was built for publication: Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
