Abstract
We conduct an experimental evaluation of all major online graph traversal algorithms. This includes many simple natural algorithms as well as more sophisticated strategies. The observations we made watching the animated algorithms explore the graphs in the interactive experiments motivated us to introduce some variants of the original algorithms. Since the theoretical bounds for deterministic online algorithms are rather bad and no better bounds for randomized algorithms are known, our work helps to provide a better insight into the practical performance of these algorithms on various graph families. It is to observe that all the tested algorithm have a performance very close to the optimum offline algorithm in a huge family of random graphs. Only few very specific lower bound examples cause bad results.
The work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. HKUST6010/01E)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Albers and M. R. Henzinger. Exploring unknown environments. SIAM Journal on Computing, 29(4):1164–1188, 2000.
S. Albers and B. Schröder. An experimental study of online scheduling algorithms. In Proceedings of the 4th Workshop of Algorithms and Engineering (WAE’00). Springer Lecture Notes in Computer Science 1982, pages 11–22, 2000.
R. Bachrach and R. El-Yaniv. Online list accessing algorithms and their applications: recent empirical evidence. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA’97), pages 53–62, 1997.
A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
X. Deng and C. H. Papadimitriou. Exploring an unknown graph. In Proceedings of the 31st Symposium on Foundations of Computer Science (FOCS’90), pages 355–361, 1990.
J. Edmonds and E. L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5:88–124, 1973.
A. Fiat and G. J. Woeginger, editors. Online Algorithms — The State of the Art. Springer Lecture Notes in Computer Science 1442, 1998.
Jesus M. Salvo Jr. Opengraph — java graph and graph drawing project. 2000. http://openjgraph.sourceforge.net/.
C. H. Papadimitriou. On the complexity of edge traversing. Journal of the ACM, 23(3):544–554, 1976.
D. Sleator and R. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202–208, 1985.
Harold Thimbleby. The directed Chinese postman problem. Technical report. http://www.uclic.ucl.ac.uk/harold/cpp/index.html.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fleischer, R., Trippen, G. (2003). Experimental Studies of Graph Traversal Algorithms. In: Jansen, K., Margraf, M., Mastrolilli, M., Rolim, J.D.P. (eds) Experimental and Efficient Algorithms. WEA 2003. Lecture Notes in Computer Science, vol 2647. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44867-5_10
Download citation
DOI: https://doi.org/10.1007/3-540-44867-5_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40205-3
Online ISBN: 978-3-540-44867-9
eBook Packages: Springer Book Archive