tr-announce

Download

tr-announce@lists.rwth-aachen.de

March 2009

1 participants
2 discussions

2009-07: Derandomizing Non-uniform Color-Coding I
by Carsten Fuhs 30 Mar '09

30 Mar '09

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.

1 0

-2009-05: A New Intersection Model and Improved Algorithms for Tolerance Graphs
by Carsten Fuhs 24 Mar '09

24 Mar '09

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.

1 0