Access Restriction

Author Frigioni, Daniele ♦ Ioffreda, Mario ♦ Nanni, Umberto ♦ Pasqualone, Giulio
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Dynamic algorithms ♦ Experimental analysis of algorithms ♦ Shortest paths
Abstract In this paper we propose the first experimental study of the fully dynamic single-source shortest-paths problem on directed graphs with positive real edge weights. In particular, we perform an experimental analysis of three different algorithms: Dijkstra's algorithm, and the two output bounded algorithms proposed by Ramalingam and Reps in [30] and by Frigioni, Marchetti-Spaccamela and Nanni in [18], respectively. The main goal of this paper is to provide a first experimental evidence for: $(\textit{a})$ the effectiveness of dynamic algorithms for shortest paths with respect to a traditional static approach to this problem; $(\textit{b})$ the validity of the theoretical model of output boundedness to analyze dynamic graph algorithms. Beside random generated graphs, useful to capture the "asymptotic" behavior of the algorithms, we also developed experiments by considering a widely used graph from the real world, i.e., the Internet graph.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1998-09-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 3

Open content in new tab

   Open content in new tab
Source: ACM Digital Library