Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality

DOI10.7155/jgaa.00619zbMath1518.05052OpenAlexW3164090850MaRDI QIDQ6107024

André Nichterlein, Rolf Niedermeier, Hendrik Molter, Maciej Rymar

Publication date: 3 July 2023

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00619

zbMATH Keywords

network sciencecounting complexitytemporal graphsnetwork centrality measurestemporal paths and walks

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Betweenness in time dependent networks
• Scalable computational techniques for centrality metrics on temporally detailed social network
• Fast approximation of betweenness centrality through sampling
• Finding temporal paths under waiting time constraints
• The complexity of finding small separators in temporal graphs
• Graphs, dioids and semirings. New models and algorithms.
• Algebraic structures for dynamic networks
• Towards classifying the polynomial-time solvability of temporal betweenness centrality
• A faster algorithm for betweenness centrality*
• On a routing problem
• The Complexity of Enumeration and Reliability Problems
• Topology manipulations for speeding betweenness centrality computation
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Better Approximation of Betweenness Centrality
• Approximating Betweenness Centrality
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• Computing Betweenness Centrality in Link Streams

This page was built for publication: Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality