31 citations · 66 across the 12 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
cs.DM2018★ 5 cited
Graphs without a partition into two proportionally dense subgraphs
Cristina Bazgan, Janka Chlebíková, Clément Dallard
A \emph{proportionally dense subgraph} (PDS) is an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the s…
cs.CC2018
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…