Better Approximation of Betweenness Centrality

DOI10.1137/1.9781611972887.9zbMath1428.68213MaRDI QIDQ5233512

Dominik Schultes, Robert Geisberger, Peter Sanders

Publication date: 11 September 2019

Published in: 2008 Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

Related Items

Improving the Betweenness Centrality of a Node by Adding Links, Dynamic Merging of Frontiers for Accelerating the Evaluation of Betweenness Centrality, Fully Dynamic 2-Hop Cover Labeling, A Faster Algorithm to Update Betweenness Centrality After Node Alteration, Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs, An Adaptive Version of Brandes' Algorithm for Betweenness Centrality, ReHub, Approximating Betweenness Centrality in Fully Dynamic Networks, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality, Some results on approximate 1-median selection in metric spaces, On the maximum betweenness improvement problem, Fast approximation of betweenness centrality through sampling, Efficient algorithms for updating betweenness centrality in fully dynamic graphs, Incorporating auxiliary information in betweenness measure for input-output networks, Towards classifying the polynomial-time solvability of temporal betweenness centrality, A Faster Algorithm to Update Betweenness Centrality after Node Alteration, Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks