31 citations · 66 across the 12 of their papers we have counts for
6 papers · 1 filter
Destroying Densest Subgraphs is Hard
Cristina Bazgan, André Nichterlein, Sofia Vazquez Alferez
We analyze the computational complexity of the following computational problems called Bounded-Density Edge Deletion and Bounded-Density Vertex Deletion: Given a graph , a budge…
One-Exact Approximate Pareto Sets
Arne Herzel, Cristina Bazgan, Stefan Ruzika +2
Papadimitriou and Yannakakis show that the polynomial-time solvability of a certain singleobjective problem determines the class of multiobjective optimization problems that admit…
The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems
Cristina Bazgan, Stefan Ruzika, Clemens Thielen +1
We determine the power of the weighted sum scalarization with respect to the computation of approximations for general multiobjective minimization and maximization problems. Additi…
Parameterized and Approximation Complexity of Partial VC Dimension
Cristina Bazgan, Florent Foucaud, Florian Sikora
We introduce the problem Partial VC Dimension that asks, given a hypergraph and integers and , whether one can select a set of vertices of $H…
Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms
Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin +1
Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a s…
Parameterized Approximability of Maximizing the Spread of Influence in Networks
Cristina Bazgan, Morgan Chopin, André Nichterlein +1
In this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value~ attached to each vertex~, th…