Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Henning Fernau:

TR06-072 | 25th February 2006
Henning Fernau

Parameterized Algorithms for Hitting Set: the Weighted Case

We are going to analyze simple search tree algorithms
for Weighted d-Hitting Set. Although the algorithms are simple, their analysis is technically rather involved. However, this approach allows us to even improve on elsewhere published algorithm running time estimates for the more restricted case of (unweighted) d-Hitting Set.

... more >>>

TR04-078 | 3rd August 2004
Henning Fernau

Two-Layer Planarization: Improving on Parameterized Algorithmics

A bipartite graph is biplanar if the vertices can be
placed on two parallel lines in the plane such that there are
no edge crossings when edges are drawn as straight-line segments.
We study two variants of biplanarization problems:
- Two-Layer Planarization TLP: can $k$ edges be deleted from
a ... more >>>

TR04-073 | 9th July 2004
Henning Fernau

A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set

In this paper, we show how to systematically
improve on parameterized algorithms and their
analysis, focusing on search-tree based algorithms
for d-Hitting Set, especially for d=3.
We concentrate on algorithms which are easy to implement,
in contrast with the highly sophisticated algorithms
which have been elsewhere designed to ... more >>>

TR04-027 | 20th February 2004
Henning Fernau

Parametric Duality: Kernel Sizes and Algorithmics

We derive the first lower bound results on kernel sizes of parameterized problems. The same idea also allows us to sometimes "de-parameterize"
parameterized algorithms.

more >>>

TR01-023 | 13th March 2001
Jochen Alber, Henning Fernau, Rolf Niedermeier

Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revisions: 1

A parameterized problem is called fixed parameter tractable
if it admits a solving algorithm whose running time on
input instance $(I,k)$ is $f(k) \cdot |I|^\alpha$, where $f$
is an arbitrary function depending only on~$k$. Typically,
$f$ is some exponential function, e.g., $f(k)=c^k$ for ... more >>>

ISSN 1433-8092 | Imprint