Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Listing All Maximal -Plexes in Temporal Graphs
Matthias Bentert, Anne-Sophie Himmel, Hendrik Molter +3
Many real-world networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (…
cs.DS2018
Parameterized Complexity of Diameter
Matthias Bentert, André Nichterlein
Diameter -- the task of computing the length of a longest shortest path -- is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no $O(n^{1.99})…
cs.DS2018
An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
Matthias Bentert, Alexander Dittmann, Leon Kellerhals +2
Betweenness centrality---measuring how many shortest paths pass through a vertex---is one of the most important network analysis concepts for assessing the relative importance of a…