An Adaptive Version of Brandes' Algorithm for Betweenness Centrality

DOI10.4230/LIPICS.ISAAC.2018.36MaRDI QIDQ5091028zbMATH OpenOpenAlexFDO

Authors Matthias Bentert, Alexander J. Dittmann, Leon Kellerhals, André Nichterlein, Rolf Niedermeier

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.ISAAC.2018.36

zbMATH Keywords

centrality measuresefficient pre- and postprocessingFPT in Pnetwork scienceshortest pathssocial network analysistree-like graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Approximating Betweenness Centrality
• Betweenness centrality -- incremental and faster
• Fully dynamic betweenness centrality
• A faster algorithm for betweenness centrality*

Cites work

• A faster algorithm for betweenness centrality*
• On tractable cases of target set selection
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Subcubic equivalences between graph centrality problems, APSP and diameter
• Who is the best connected scientist? A study of scientific coauthorship networks

Cited in

(3)

• A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• When can graph hyperbolicity be computed in linear time?

This page was built for publication: An Adaptive Version of Brandes' Algorithm for Betweenness Centrality

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