Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality

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 s...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph algorithms and applications 2023-05, Vol.27 (3), p.173-194
Main Authors: Rymar, Maciej, Molter, Hendrik, Nichterlein, André, Niedermeier, Rolf
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1526-1719
1526-1719
DOI:10.7155/jgaa.00619