1 citations · 2 across the 7 of their papers we have counts for
3 papers · 1 filter
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…
When can Graph Hyperbolicity be computed in Linear Time?
Till Fluschnik, Christian Komusiewicz, George B. Mertzios +3
Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen int…
On the Parameterized and Approximation Hardness of Metric Dimension
Sepp Hartung, André Nichterlein
The NP-hard Metric Dimension problem is to decide for a given graph G and a positive integer k whether there is a vertex subset of size at most k that separates all vertex pairs in…