31 citations · 66 across the 12 of their papers we have counts for
5 papers · 1 filter
Dense Graph Partitioning on sparse and dense graphs
Cristina Bazgan, Katrin Casel, Pierre Cazals
We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of t…
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…
Parameterized Inapproximability of Target Set Selection and Generalizations
Cristina Bazgan, Morgan Chopin, André Nichterlein +1
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value for any vertex of the graph, find a minimum size vertex-subset to "act…