31 citations · 116 across the 28 of their papers we have counts for
4 papers · 1 filter
Constant-factor approximations for Capacitated Arc Routing without triangle inequality
René van Bevern, Sepp Hartung, André Nichterlein +1
Given an undirected graph with edge costs and edge demands, the Capacitated Arc Routing problem (CARP) asks for minimum-cost routes for equal-capacity vehicles so as to satisfy all…
Win-Win Kernelization for Degree Sequence Completion Problems
Vincent Froese, André Nichterlein, Rolf Niedermeier
We study provably effective and efficient data reduction for a class of NP-hard graph modification problems based on vertex degree properties. We show fixed-parameter tractability…
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…
Improved Upper and Lower Bound Heuristics for Degree Anonymization in Social Networks
Sepp Hartung, Clemens Hoffmann, André Nichterlein
Motivated by a strongly growing interest in anonymizing social network data, we investigate the NP-hard Degree Anonymization problem: given an undirected graph, the task is to add…