Source author record

Frank Kammer

Frank Kammer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Computational Geometry

Catalog footprint

What is connected

4works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Multistage Graph Problems on a Global Budget

Time-evolving or temporal graphs gain more and more popularity when studying the behavior of complex networks. In this context, the multistage view on computational problems is among the most natural frameworks. Roughly speaking, herein one studies the different (time) layers of a temporal graph (effectively meaning that the edge set may change over time, but the vertex set remains unchanged), and one searches for a solution of a given graph problem for each layer. The twist in the multistage setting is that the solutions found must not differ too much between subsequent layers. We relax on this already established notion by introducing a global instead of the local budget view studied so far. More specifically, we allow for few disruptive changes between subsequent layers but request that overall, that is, summing over all layers, the degree of change is moderate. Studying several classical graph problems (both NP-hard and polynomial-time solvable ones) from a parameterized complexity angle, we encounter both fixed-parameter tractability and parameterized hardness results. Somewhat surprisingly, we find that sometimes the global multistage versions of NP-hard problems such as Vertex Cover turn out to be computationally more tractable than the ones of polynomial-time solvable problems such as Matching.

preprint2016arXiv

Approximate Tree Decompositions of Planar Graphs in Linear Time

Many algorithms have been developed for NP-hard problems on graphs with small treewidth $k$. For example, all problems that are expressable in linear extended monadic second order can be solved in linear time on graphs of bounded treewidth. It turns out that the bottleneck of many algorithms for NP-hard problems is the computation of a tree decomposition of width $O(k)$. In particular, by the bidimensional theory, there are many linear extended monadic second order problems that can be solved on $n$-vertex planar graphs with treewidth $k$ in a time linear in $n$ and subexponential in $k$ if a tree decomposition of width $O(k)$ can be found in such a time. We present the first algorithm that, on $n$-vertex planar graphs with treewidth $k$, finds a tree decomposition of width $O(k)$ in such a time. In more detail, our algorithm has a running time of $O(n k^2 \log k)$. We show the result as a special case of a result concerning so-called weighted treewidth of weighted graphs.

preprint2016arXiv

Space-Efficient Plane-Sweep Algorithms

We introduce space-efficient plane-sweep algorithms for basic planar geometric problems. It is assumed that the input is in a read-only array of $n$ items and that the available workspace is $Θ(s)$ bits, where $\lg n \leq s \leq n \cdot \lg n$. Three techniques that can be used as general tools in different space-efficient algorithms are introduced and employed within our algorithms. In particular, we give an almost-optimal algorithm for finding the closest pair among a set of $n$ points that runs in $O(n^2/s + n \cdot \lg s)$ time. We also give a simple algorithm to enumerate the intersections of $n$ line segments that runs in $O((n^2/s^{2/3}) \cdot \lg s + k)$ time, where $k$ is the number of intersections. The counting version can be solved in $O((n^2/s^{2/3}) \cdot \lg s)$~time. When the segments are axis-parallel, we give an $O((n^2/s) \cdot \lg^{4/3} s + n^{4/3} \cdot \lg^{1/3} n)$-time algorithm for counting the intersections, and an algorithm for enumerating the intersections that runs in $O((n^2/s) \cdot \lg s \cdot \lg \lg s + n \cdot \lg s + k)$ time, where $k$ is the number of intersections. We finally present an algorithm that runs in $O((n^2/s + n \cdot \lg s) \cdot \sqrt{(n/s) \cdot \lg n})$ time to calculate Klee's measure of axis-parallel rectangles.

preprint2011arXiv

Removing Local Extrema from Imprecise Terrains

In this paper we consider imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. In particular, we study the problem of removing as many local extrema (minima and maxima) as possible from the terrain. We show that removing only minima or only maxima can be done optimally in O(n log n) time, for a terrain with n vertices. Interestingly, however, removing both the minima and maxima simultaneously is NP-hard, and is even hard to approximate within a factor of O(log log n) unless P=NP. Moreover, we show that even a simplified version of the problem where vertices can have only two different heights is already NP-hard, a result we obtain by proving hardness of a special case of 2-Disjoint Connected Subgraphs, a problem that has lately received considerable attention from the graph-algorithms community.