20 citations · 33 across the 6 of their papers we have counts for
7 papers
Fixed-Parameter Algorithms for DAG Partitioning
René van Bevern, Robert Bredereck, Morgan Chopin +4
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 2009] as DAG Partitioning: given an arc-weighted directed acyclic…
Co-Clustering Under the Maximum Norm
Laurent Bulteau, Vincent Froese, Sepp Hartung +1
Co-clustering, that is, partitioning a numerical matrix into homogeneous submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting varia…
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…
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…
On Structural Parameterizations for the 2-Club Problem
Sepp Hartung, Christian Komusiewicz, André Nichterlein +1
The NP-hard 2-Club problem is, given an undirected graph G=(V,E) and l\in N, to decide whether there is a vertex set S\subseteq V of size at least l such that the induced subgraph…
On the Parameterized and Approximation Hardness of Metric Dimension
Sepp Hartung, André Nichterlein
The NP-hard Metric Dimension problem is to decide for a given graph G and a positive integer k whether there is a vertex subset of size at most k that separates all vertex pairs in…
NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
Sepp Hartung, André Nichterlein
In graph realization problems one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match to the given sequence. This realization p…