All reports by Author Henning Fernau:

__
TR06-072
| 25th February 2006
__

Henning Fernau#### Parameterized Algorithms for Hitting Set: the Weighted Case

__
TR04-078
| 3rd August 2004
__

Henning Fernau#### Two-Layer Planarization: Improving on Parameterized Algorithmics

__
TR04-073
| 9th July 2004
__

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

__
TR04-027
| 20th February 2004
__

Henning Fernau#### Parametric Duality: Kernel Sizes and Algorithmics

__
TR01-023
| 13th March 2001
__

Jochen Alber, Henning Fernau, Rolf Niedermeier#### Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revisions: 1

Henning Fernau

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.

Henning Fernau

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

Henning Fernau

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

Henning Fernau

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.

Jochen Alber, Henning Fernau, Rolf Niedermeier

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