Home Pages - Panagiota Fatourou

Projects

LEDA

The algorithm GCOMPONENTS has been implemented in LEDA.GCOMPONENTS achieves to find the connected components of a graph G = (V,E) in O(|V|) expected time. The best algorithm for finding the connected components in a graph requires time O(|V|+|E|) in the worst case. Such an algorithm called COMPONENTS, is implemented in LEDA. Proper measurements of the performance of these two algorithms have been done and GCOMPONENTS behaves better than COMPONENTS for graphs with a large edge set. Besides the implementation of GCOMPONENTS, a graphical user interface has been created that simplifies its execution, while simultaneously, can be used for the demonstration of its use. A technical document ([1], click here for postscript file) has been produced that describes the implementation of GCOMPONENTS, its testing,the user interface, and the measurements that have been selected.

Moreover, the polylogarithmic dynamic graph connectivity algorithm by Nikoletseas, Reif, Spirakis and Yung [4] has been implemented. The algorithm can cope with any random sequence of three kinds of operations:

• Property-Query(parameter): Returns true if and only if the property holds (or returns a subgraph as a witness to the property). For a connectivity query (u,v), a true answer means that the vertices u, v are in the same connected component.
• Insert(x,y): Insert a new edge joining x to y (assuming that {x,y}\in E).
• Delete(x,y): Deletes the edge {x,y} (assuming {x,y} \in E).

A version of the code is now available: click here for downloading.

A paper (gziped postscript) describing the implementation of the algorithm and its experimental evaluation is now available.

REFERENCES

[1] P. Fatourou, G. Pantziou, P. Spirakis, P. Zarafidis and A. Zoura, ``Implementation of a Linear Expected-Time Algorithm for Finding Connected Components'', CTI-T.R. 97.11.42 (http://helios.cti.gr/alcom-it/leda).

[2] P. Fatourou, P. Spirakis, P. Zarafidis and A. Zoura, ``Implementation and Experimental Evaluation of Graph Connectivity Algorithms using LEDA'', submitted for publication (http://helios.cti.gr/alcom-it/leda, gziped postscript).

[3] R. Karp and R. Tarjan, ``Linear Expected Time for Connectivity Problems'', In Proceedings of the 12th STOC, 1980.

[4] S. Nikoletseas, J. Reif, P. Spirakis and M. Young, ``Stochastic Graphs Have Short Memory: Fully Dynamic Connectivity in Poly-Log Expected Time'', In Proceedings of the 22nd ICALP, pp. 159-170, 1995.

PAROS

Design of Efficient Algorithms for the Dynamic Load Balancing and Scheduling of Multithreaded Computations [5].

[5] Panagiota Fatourou and Paul Spirakis, ``Scheduling Algorithms for Strict Multithreaded Computations’’, Proceedings of the 7^th Annual Symposium on Algorithms and Computation (ISAAC ’96), pp. 407 - 416, Japan, December 1996.

Link to the coordinating site's web page for PAROS.

FRAMES

A Shared Memory Simulation Frame (SMS-Frame) will be implemented. The SMS-Frame will give the opportunity of executing parallel algorithms designed for a variant of PRAM, over a purely distributed working environment, that will be considered to comply with the DMM model. The reason why the models of PRAM and DMM have been chosen, is that the former has proved to be the most popular cost model in the parallel algorithms community, while the latter is an abstracted model based on message passing, that is very close to, or is provided through specialized interfaces by the majority of the vendors of parallel machines.
For more information, see http://helios.cti.gr/frames/.