1 citations · 2 across the 11 of their papers we have counts for
5 papers · 1 filter
Parameterized Dynamic Cluster Editing
Junjie Luo, Hendrik Molter, André Nichterlein +1
We introduce a dynamic version of the NP-hard graph problem Cluster Editing. The essential point here is to take into account dynamically evolving input graphs: Having a cluster gr…
Exact Algorithms for Finding Well-Connected 2-Clubs in Real-World Graphs: Theory and Experiments
Christian Komusiewicz, André Nichterlein, Rolf Niedermeier +1
Finding large "cliquish" subgraphs is a central topic in graph mining and community detection. A popular clique relaxation are 2-clubs: instead of asking for subgraphs of diameter…
A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
Cristina Bazgan, Till Fluschnik, André Nichterlein +2
We study the NP-hard Shortest Path Most Vital Edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and t…
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})…
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…