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