Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-073 | 9th July 2004 00:00

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

RSS-Feed




TR04-073
Authors: Henning Fernau
Publication: 24th August 2004 14:22
Downloads: 3982
Keywords: 


Abstract:

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 improve on
the exponential base in the algorithms.

The algorithm analysis is based on a novel way to exploit
a so-called auxiliary parameter, a technique which we believe
can be used in other circumstances, as well.



ISSN 1433-8092 | Imprint