Subcubic equivalences between graph centrality problems, APSP and diameter

DOI10.1137/1.9781611973730.112MaRDI QIDQ5363057zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Network Analysis
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Approximating Betweenness Centrality
• Fast Approximation of Centrality
• STACS 2005

Cited in

(36)

• The fine-grained complexity of multi-dimensional ordering properties
• An efficient noisy binary search in graphs via Median approximation
• Medians in median graphs and their cube complexes in linear time
• Equivalence classes and conditional hardness in massively parallel computations
• Eccentricity queries and beyond using hub labels
• Improved distance queries and cycle counting by Frobenius normal form
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• A note on the complexity of computing the number of reachable vertices in a digraph
• New results and open problems on subgraph centrality
• Computing giant graph diameters
• On the power of tree-depth for fully polynomial FPT algorithms
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• Towards hardness of approximation for polynomial time problems
• Conditional hardness for sensitivity problems
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• From circuit complexity to faster all-pairs shortest paths
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Approximation algorithms for min-distance problems
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• 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
• Medians in median graphs and their cube complexes in linear time
• On the fine-grained complexity of parity problems
• Approximation algorithms for min-distance problems in DAGs
• Into the square: on the complexity of some quadratic-time solvable problems

This page was built for publication: Subcubic equivalences between graph centrality problems, APSP and diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363057)