1 citations · 1 across the 2 of their papers we have counts for
3 papers · 1 filter
Proportionally dense subgraph of maximum size: complexity and approximation
Cristina Bazgan, Janka Chlebíková, Clément Dallard +1
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in th…
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…
Algorithmic Aspects of Upper Domination
Cristina Bazgan, Ljiljana Brankovic, Katrin Casel +6
In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a…