FG Algorithmik und Komplexitätstheorie

10 Items

Recent Submissions
Efficient computation of optimal temporal walks under waiting-time constraints

Bentert, Matthias ; Himmel, Anne-Sophie ; Nichterlein, André ; Niedermeier, Rolf (2020-10-06)

Node connectivity plays a central role in temporal network analysis. We provide a broad study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but arc sets changing over time. Taking into account the temporal aspect leads to a rich set of optimization criteria for “shortest” walks. Extending and broadening state-of-the-art work of Wu et al. [IEEE TKDE 2016...

Parameterized dynamic cluster editing

Luo, Junjie ; Molter, Hendrik ; Nichterlein, André ; Niedermeier, Rolf (2020-07-25)

We introduce a dynamic version of the NP -hard graph modification problem Cluster Editing . The essential point here is to take into account dynamically evolving input graphs: having a cluster graph (that is, a disjoint union of cliques) constituting a solution for a first input graph, can we cost-efficiently transform it into a “similar” cluster graph that is a solution for a second (“subseque...

The power of linear-time data reduction for maximum matching

Mertzios, George B. ; Nichterlein, André ; Niedermeier, Rolf (2020-07-06)

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m -edge and n -vertex graphs, it is well-known to be solvable in O(m\sqrt{n})  time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. ...

A fast shortest path algorithm on terrain-like graphs

Froese, Vincent ; Renken, Malte (2020-08-04)

Terrain visibility graphs are a well-known graph class in computational geometry. They are closely related to polygon visibility graphs, but a precise graph-theoretical characterization is still unknown. Over the last decade, terrain visibility graphs attracted considerable attention in the context of time series analysis (there called time series visibility graphs) with various practical appli...

Comparing temporal graphs using dynamic time warping

Froese, Vincent ; Jain, Brijnesh ; Niedermeier, Rolf ; Renken, Malte (2020-06-29)

Within many real-world networks, the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal graphs requires a proximity measure to compare different temporal graphs. To this end, we propose to study dynamic time warping on temporal graphs. We define the dynamic temporal graph warping (dtgw) distance to dete...

h-Index manipulation by undoing merges

Bevern, René van ; Komusiewicz, Christian ; Molter, Hendrik ; Niedermeier, Rolf (2020-12-30)

The h-index is an important bibliographic measure used to assess the performance of researchers. Dutiful researchers merge different versions of their articles in their Google Scholar profile even though this can decrease their h-index. In this article, we study the manipulation of the h-index by undoing such merges. In contrast to manipulation by merging articles, such manipulation is harder t...

Classic graph problems made temporal – a parameterized complexity analysis

Molter, Hendrik (2020)

This thesis investigates the parameterized computational complexity of six classic graph problems lifted to a temporal setting. More specifically, we consider problems defined on temporal graphs, that is, a graph where the edge set may change over a discrete time interval, while the vertex set remains unchanged. Temporal graphs are well-suited to model dynamic data and hence they are naturally ...

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...