Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00619
Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality
Maciej Rymar,
Hendrik Molter,
André Nichterlein, and
Rolf Niedermeier
Vol. 27, no. 3, pp. 173-194, 2023. Regular paper.
Abstract In static graphs, the betweenness centrality of a graph vertex measures
how many times this vertex is part of a shortest path between
any two graph vertices. Betweenness centrality is efficiently computable and
it is a fundamental tool in network science. Continuing and extending previous
work, we study the efficient computability of betweenness centrality in
temporal graphs (graphs with fixed vertex set but time-varying
edge sets). Unlike in the static case, there
are numerous natural notions of being a ''shortest'' temporal path (walk).
Depending on which notion is used, it was already observed
that the problem is #P-hard in some cases while polynomial-time solvable
in others. In this conceptual work, we contribute towards classifying
what a ''shortest path (walk) concept'' has to fulfill in
order to gain polynomial-time computability of temporal betweenness centrality.
This work is licensed under the terms of the CC-BY license.
|
Submitted: August 2021.
Reviewed: July 2022.
Revised: October 2022.
Accepted: February 2023.
Final: March 2023.
Published: May 2023.
Communicated by
Ulrik Brandes
|
Journal Supporters
|