Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter

DOI10.1137/1.9781611973730.112zbMath1371.68203OpenAlexW4249997060MaRDI QIDQ5363057

Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.112

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (31)

Medians in median graphs and their cube complexes in linear time ⋮ Equivalence classes and conditional hardness in massively parallel computations ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ A note on the complexity of computing the number of reachable vertices in a digraph ⋮ Eccentricity queries and beyond using hub labels ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ An Adaptive Version of Brandes' Algorithm for Betweenness Centrality ⋮ Unnamed Item ⋮ On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions ⋮ Computation of diameter, radius and center of permutation graphs ⋮ Graphs with \(G^p\)-connected medians ⋮ Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ A fast output-sensitive algorithm for Boolean matrix multiplication ⋮ Unnamed Item ⋮ An Adaptive Version of Brandes' Algorithm for Betweenness Centrality ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Unnamed Item ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Computing Giant Graph Diameters ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An efficient noisy binary search in graphs via Median approximation

This page was built for publication: Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter