Thumbnail
Access Restriction
Subscribed

Author Krommidas, Ioannis ♦ Zaroliagis, Christos
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Transitive closure ♦ Dynamic algorithm ♦ Path ♦ Reachability
Abstract We have conducted an extensive experimental study on algorithms for fully dynamic transitive closure. We have implemented the recent fully dynamic algorithms by King [1999], Roditty [2003], Roditty and Zwick [2002, 2004], and Demetrescu and Italiano [2000, 2005] along with several variants and compared them to pseudo fully dynamic and simple-minded algorithms developed in a previous study [Frigioni et al. 2001]. We tested and compared these implementations on random inputs, synthetic (worst-case) inputs, and on inputs motivated by real-world graphs. Our experiments reveal that some of the dynamic algorithms can really be of practical value in many situations.
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 2008-06-12
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 12
Page Count 22
Starting Page 1
Ending Page 22


Open content in new tab

   Open content in new tab
Source: ACM Digital Library