31 citations · 66 across the 12 of their papers we have counts for
15 papers
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…
Approximating Multiobjective Optimization Problems: How exact can you be?
Cristina Bazgan, Arne Herzel, Stefan Ruzika +2
It is well known that, under very weak assumptions, multiobjective optimization problems admit -approximation sets (also called -P…
Exact and approximate determination of the Pareto set using minimal correction subsets
Andreia P. Guerreiro, João Cortes, Daniel Vanderpooten +4
Recently, it has been shown that the enumeration of Minimal Correction Subsets (MCS) of Boolean formulas allows solving Multi-Objective Boolean Optimization (MOBO) formulations. Ho…
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…
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…