2026-07-22T13:04:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9984 2024-03-06T10:45:16Z ddc:004 open_access

An Adaptive Version of Brandes' Algorithm for Betweenness Centrality Bentert, Matthias Dittmann, Alexander Kellerhals, Leon Nichterlein, André Niedermeier, Rolf network science social network analysis centrality measures shortest paths tree-like graphs efficient pre- and postprocessing FPT in P Betweenness centrality - measuring how many shortest paths pass through a vertex - is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [2001] computes, on an n-vertex and m-edge graph, the betweenness centrality of all vertices in O(nm) worst-case time. In follow-up work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We further contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound O(kn), where k < m is the size of a minimum feedback edge set of the input graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Alexander Dittmann and Leon Kellerhals and André Nichterlein and Rolf Niedermeier 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.36 urn:nbn:de:0030-drops-99846 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.36 eng https://creativecommons.org/licenses/by/3.0/legalcode