FG Algorithmik und Komplexitätstheorie

3 Items

Recent Submissions
Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods

Fluschnik, Till (2020)

Preprocessing and data reduction are basic algorithmic tools. In parameterized algorithmics, such preprocessing is defined by (problem) kernelization, where an equivalent instance (the kernel) is computed in polynomial time and its size can be upper-bounded only in a function of the parameter value of the input instance. In this thesis, we study lower and upper bounds on kernelization regarding...

Co-Clustering under the Maximum Norm

Bulteau, Laurent ; Froese, Vincent ; Hartung, Sepp ; Niedermeier, Rolf (2016-02-25)

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 of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we sp...

Finding Supported Paths in Heterogeneous Networks

Fertin, Guillaume ; Komusiewicz, Christian ; Mohamed-Babou, Hafedh ; Rusu, Irena (2015-10-09)

Subnetwork mining is an essential issue in the analysis of biological, social and communication networks. Recent applications require the simultaneous mining of several networks on the same or a similar vertex set. That is, one searches for subnetworks fulfilling different properties in each input network. We study the case that the input consists of a directed graph D and an undirected graph G...