Co-Clustering under the Maximum Norm

Autor: Laurent Bulteau, Vincent Froese, Sepp Hartung, Rolf Niedermeier

Publikováno v: Algorithms, Vol 9, Iss 1, p 17 (2016)

Co-clustering, that is partitioning a numerical matrix into “homogeneous” submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant o

Externí odkaz: https://doaj.org/article/2dc6acd2b7bc47109d0548cb1732b311

Finding large degree-anonymous subgraphs is hard

Autor: Cristina Bazgan, Robert Bredereck, Sepp Hartung, Gerhard J. Woeginger, André Nichterlein

Publikováno v: Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2016, 622, ⟨10.1016/j.tcs.2016.02.004⟩
Theoretical Computer Science, 622, 90-110. Elsevier

International audience; A graph is said to be k-anonymous for an integer k, if for every vertex in the graph there are at least k−1k−1 other vertices with the same degree. We examine the computational complexity of making a given undirected graph

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::21c274bcfb8adf93c60f3edb9e8fb578
https://doi.org/10.1016/j.tcs.2016.02.004

A refined complexity analysis of degree anonymization in graphs

Autor: Ondřej Suchý, Rolf Niedermeier, André Nichterlein, Sepp Hartung

Publikováno v: Information and Computation. 243:249-262

Motivated by a strongly growing interest in graph anonymization, we study the NP-hard Degree Anonymity problem asking whether a graph can be made k-anonymous by adding at most a given number of edges. Herein, a graph is k-anonymous if for every verte

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::606c9691ff8f90e4460d4f1d4119dfbf
https://doi.org/10.1016/j.ic.2014.12.017

Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs

Autor: André Nichterlein, Sepp Hartung, Christian Komusiewicz

Publikováno v: Journal of Graph Algorithms and Applications. 19:155-190

Given an undirected graph G=(V,E) and an integer l≥1, the NP-hard 2-Club problem asks for a vertex set S⊆V of size at least l such that the subgraph induced by S has diameter at most two. In this work, we extend previous parameterized complexity

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::ce7c257276384aaec93f9927c11ce2d5
https://doi.org/10.7155/jgaa.00352

Fixed-Parameter Algorithms for DAG Partitioning

Autor: Robert Bredereck, Andr Nichterlein, Morgan Chopin, Sepp Hartung, Ondej Such, Falk Hffner, Ren van Bevern

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 graph on $n$ vertices and $m$ arcs, delete arcs with total weight at

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::22bf7cd93b501af4764f2a18b20929cf