Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality
DOI:
https://doi.org/10.7155/jgaa.00619Keywords:
temporal graphs , temporal paths and walks , network science , network centrality measures , counting complexityAbstract
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.Downloads
Download data is not yet available.
Downloads
Published
2023-05-01
How to Cite
Rymar, M., Molter, H., Nichterlein, A., & Niedermeier, R. (2023). Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality. Journal of Graph Algorithms and Applications, 27(3), 173–194. https://doi.org/10.7155/jgaa.00619
License
Copyright (c) 2023 Maciej Rymar, Hendrik Molter, André Nichterlein, Rolf Niedermeier
This work is licensed under a Creative Commons Attribution 4.0 International License.