Spanner Experimental Package
Camil Demetrescu and Andrea Ribichini
Introduction
This experimental package (SEP-1.2) has been used in the preparation of the following works, of which it is intended as an electronic companion:
-
"Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments", by
Giorgio Ausiello, Camil Demetrescu, Paolo G. Franciosa, Giuseppe F.
Italiano and Andrea Ribichini; conference paper, published in the Proceedings of the 15th Annual European
Symposium on Algorithms (ESA'07).
- "Streaming Algorithms for Graph Problems",
by Andrea Ribichini; PhD thesis.
-
"Graph Spanners in the Streaming Model: an Experimental Study", by
Giorgio Ausiello, Camil Demetrescu, Paolo G. Franciosa, Giuseppe F.
Italiano and Andrea Ribichini; journal article, published in Algorithmica, Volume 55, Number 2 (October 2009), pages 346-374, Springer New York.
The package includes:
- Implementations of the algorithms discussed in the above works, for producing spanners of unweighted and undirected graphs.
- Synthetic graph generators and various utilities for comparing spanners and original graphs.
- Various charts summarizing our experimental results.
The software package is implemented in C/C++ (using POSIX system calls) and is based on, and
includes portions of, the Leonardo Library (LL).
License
Unless otherwise stated, all programs in this package are distributed under the GNU General Public License (GPL).
The Leonardo Library is distributed under the GNU Lesser General Public License (LGPL).
Download
Download SEP-1.2 software package, http, tar.gz, 227KB [README] (the package includes portions of the Leonardo Library)