Aigaion: RACTI / RU1 Technical Report Series (Web Based)

[RACTI-RU1-2007-89] Caragiannis, Ioannis, Flamini, M and Moscardelli, L, An exponential improvement to the MST heuristic for minimum energy broadcasting in ad hoc wireless networks, in: 34th International Colloquium on Automata, Languages, and Programming (ICALP 2007), Springer, 2007.
Abstract: In this paper we present a new approximation algorithm for the Minimum Energy Broadcast Routing (MEBR) problem in ad hoc wireless networks that has exponentially better approximation factor than the well-known Minimum Spanning Tree (MST) heuristic. Namely, for any instance where a minimum spanning tree of the set of stations is guaranteed to cost at most � times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ra- tio bounded by 2 ln � � 2 ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we signi�cantly improve previous results.
[RACTI-RU1-2002-20] Zaroliagis, Christos, Implementations and Experimental Studies of Dynamic Graph Algorithms, in: Experimental Algorithmics - From Algorithm Design to Robust and Efficient Software, pages 229-278, Springer-Verlag, 2002.
Abstract: Dynamic graph algorithms have been extensively studied in the last two decades due to their wide applicabilityin manycon texts. Recently, several implementations and experimental studies have been conducted investigating the practical merits of fundamental techniques and algorithms. In most cases, these algorithms required sophisticated engineering and fine-tuning to be turned into efficient implementations. In this paper, we surveysev - eral implementations along with their experimental studies for dynamic problems on undirected and directed graphs. The former case includes dynamic connectivity, dynamic minimum spanning trees, and the sparsification technique. The latter case includes dynamic transitive closure and dynamic shortest paths. We also discuss the design and implementation of a software libraryfor dynamic graph algorithms.
[RACTI-RU1-1998-7] Zaroliagis, Christos, Parallel Processing Letters, in: Parallel Processing Letters, volume 7, number 1, pages 25-37, 1998.
Abstract: Two simple and work-efficient parallel algorithms for the minimum spanning tree problem are presented. Both algorithms perform O( m log n ) work. The first algorithm runs in O( log^2 n ) time on an EREW PRAM while the second algorithm runs in O( log n ) time on a Common CRCW PRAM.