×

Implementations and experimental studies of dynamic graph algorithms. (English) Zbl 1026.68829

Fleischer, Rudolf (ed.) et al., Experimental algorithmics. From algorithm design to robust and efficient software. Berlin: Springer. Lect. Notes Comput. Sci. 2547, 229-278 (2002).
Summary: Dynamic graph algorithms have been extensively studied in the last two decades due to their wide applicability in many contexts. 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 survey several 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 library for dynamic graph algorithms.
For the entire collection see [Zbl 1011.68694].

MSC:

68U99 Computing methodologies and applications
68W05 Nonnumerical algorithms
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)

Software:

Balibase
PDFBibTeX XMLCite
Full Text: Link