The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Derandomizing Non-uniform Color-Coding I
Joachim Kneis, Alexander Langer, Peter Rossmanith
AIB 2009-07
Color-coding, as introduced by Alon, Yuster, and Zwick, is a well-known
tool for algorithm design and can often be efficiently derandomized using
universal hash functions. In the special case of only two colors, one
can use (n,k)-universal sets for the derandomization. In this paper,
we introduce (n,k,l)-universal sets that are typically smaller and can
be constructed faster. Nevertheless, for some problems they are still
sufficient for derandomization and faster deterministic algorithms can
be obtained. This particularly works well when the color-coding does
not use a uniform probability distribution. To exemplify the concept, we
present an algorithm for the Unique Coverage problem introduced
by Demaine, Feige, Hajiaghayi, and Salavatipour. The example also shows
how to extend the concept to multiple colors.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
A New Intersection Model and Improved Algorithms for Tolerance Graphs
George B. Mertzios, Ignasi Sau, Shmuel Zaks
AIB 2009-05
Tolerance graphs model interval relations in such a way that intervals
can tolerate a certain degree of overlap without being in conflict. This
class of graphs, which generalizes in a natural way both interval and
permutation graphs, has attracted many research efforts since their
introduction in~\cite{GoMo82}, as it finds many important applications
in constraint-based temporal reasoning, resource allocation, and
scheduling problems, among others. In this article we propose the first
non-trivial intersection model for general tolerance graphs, given by
three-dimensional parallelepipeds, which extends the widely known
intersection model of parallelograms in the plane that characterizes the
class of bounded tolerance graphs. Apart from being important on its
own, this new representation also enables us to improve the time
complexity of three problems on tolerance graphs. Namely, we present
optimal $\mathcal{O}(n\log n)$ algorithms for computing a minimum
coloring and a maximum clique, and an $\mathcal{O}(n^{2})$ algorithm for
computing a maximum weight independent set in a tolerance graph with $n$
vertices, thus improving the best known running times
$\mathcal{O}(n^{2})$ and $\mathcal{O}(n^{3})$ for these problems,
respectively.
