Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter

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

zbMATH Keywords

diametermedianradiusbetweenness centralityfine-grained complexityAPSPreach centralitysubcubic reductions

Mathematics Subject Classification ID

Computer science (68-XX)

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