{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:53Z","timestamp":1750308773232,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["IST-2002-001907FP6-021235-2"],"award-info":[{"award-number":["IST-2002-001907FP6-021235-2"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1227161.1370597","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-22","source":"Crossref","is-referenced-by-count":13,"title":["An experimental study of algorithms for fully dynamic transitive closure"],"prefix":"10.1145","volume":"12","author":[{"given":"Ioannis","family":"Krommidas","sequence":"first","affiliation":[{"name":"CTI and University of Patras, Patras, Greece"}]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[{"name":"CTI and University of Patras, Patras, Greece"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. 2nd Workshop on Algorithm Engineering and Experiments\u2014ALENEX","author":"Abdeddaim S.","year":"2000","unstructured":"Abdeddaim, S. 2000. Algorithms and experiments on transitive closure, path cover and multiple sequence alignment. In Proc. 2nd Workshop on Algorithm Engineering and Experiments\u2014ALENEX 2000. 157--169.]]"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/264216.264223"},{"volume-title":"Proc. Workshop on Algorithms and Experiments\u2014ALEX'98","author":"Alberts D.","key":"e_1_2_1_3_1","unstructured":"Alberts, D., Cattaneo, G., Italiano, G., Nanni, U., and Zaroliagis, C. 1998. A software library of dynamic graph algorithms. In Proc. Workshop on Algorithms and Experiments\u2014ALEX'98. 129--136.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/314161.314314"},{"key":"e_1_2_1_5_1","volume-title":"Tech. Rep. RIPE-181. (Oct.).]]","author":"Bates T.","year":"1994","unstructured":"Bates, T., Gerich, E., Joncheray, L., Jouanigot, J.-M., Karrenberg, D., Terpstra, M., and Yu, J. 1994. Representation of ip routing policies in a routing registry. Tech. Rep. RIPE-181. (Oct.).]]"},{"volume-title":"Random Graphs","author":"Bollobas B.","key":"e_1_2_1_6_1","unstructured":"Bollobas, B. 1985. Random Graphs. Academic Press, New York.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646680.702319"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796544"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198519"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/647257.720774"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982845"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059514"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297147"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945403"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796250"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/39515.39523"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90136-6"},{"key":"e_1_2_1_19_1","volume-title":"Proc. 2nd Workshop on Algorithm Engineering and Experiments\u2014ALENEX","author":"Iyer R.","year":"2000","unstructured":"Iyer, R., Karger, D., Rahul, H., and Thorup, M. 2000. An experimental study of poly-logarithmic fully-dynamic connectivity algorithms. In Proc. 2nd Workshop on Algorithm Engineering and Experiments\u2014ALENEX 2000. 59--78.]]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796487"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301380"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/646719.702238"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_49"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/331319"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758779"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644172"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652176"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007387"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.25"},{"key":"e_1_2_1_30_1","unstructured":"Valgrind. 2006. http:\/\/valgrind.kde.org\/.]]"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/857152.857164"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370597","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1370597","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":30,"alternative-id":["10.1145\/1227161.1370597"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1370597","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}