Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2409))
Included in the following conference series:
788Accesses
Abstract
In many fields of application, shortest path finding problems in very large graphs arise. Scenarios where large numbers of on-line queries for shortest paths have to be processed in real-time appear for example in traffic information systems. In such systems, the techniques considered to speed up the shortest path computation are usually based on precomputed information. One approach proposed often in this context is a space reduction, where precomputed shortest paths are replaced by single edges with weight equal to the length of the corresponding shortest path. In this paper, we give a first systematic experimental study of such a space reduction approach. We introduce the concept of multi-level graph decomposition. For one specific application scenario from the field of timetable information in public transport, we perform a detailed analysis and experimental evaluation of shortest path computations based on multi-level graph decomposition.
This work was partially supported by the Human Potential Programme of EU under contract no. HPRN-CT-1999-00104 (AMORE), by the Future and Emerging Technologies Programme of EU under contract no. IST-1999-14186 (ALCOM-FT), and by the Deutsche Forschungsgemeinschaft under grant WA 654/12-1.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
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
R. Agrawal and H. Jagadish. Algorithms for Searching Massive Graphs.IEEE Transact. Knowledge and Data Eng., Vol. 6, 225–238, 1994.
C. Barrett, R. Jacob, and M. Marathe. Formal-Language-Constrained Path Problems.SIAM Journal on Computing, Vol. 30, No. 3, 809–837, 2000.
U. Brandes, F. Schulz, D. Wagner, and T. Willhalm. Travel Planning with Self-Made Maps.Proc. 3rd Workshop Algorithm Engineering and Experiments (ALENEX’ 01), Springer LNCS Vol. 2153, 132–144, 2001.
A. Car and A. Frank. Modelling a Hierarchy of Space Applied to Large Road Networks.Proc. Int. Worksh. Adv. Research Geogr. Inform. Syst. (IGIS’ 94), 15–24, 1994.
S. Chaudhuri and C. Zaroliagis. Shortest Paths in Digraphs of Small Treewidth. Part II: Optimal Parallel Algorithms.Theoretical Computer Science, Vol. 203, No. 2, 205–223, 1998.
S. Chaudhuri and C. Zaroliagis. Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms.Algorithmica, Vol. 27, No. 3, 212–226, Special Issue on Treewidth, 2000.
G. Frederickson. Planar graph decomposition and all pairs shortest paths.Journal of the ACM, Vol. 38, Issue 1, 162–204, 1991.
G. Frederickson. Using Cellular Graph: Embeddings in Solving All Pairs Shortest Path Problems.Journal of Algorithms, Vol. 19, 45–85, 1995.
http://bahn.hafas.de. Hafas is a trademark of Hacon Ingenieurgesellschaft mbH, Hannover, Germany.
M. Müller-Hannemann and K. Weihe. Pareto Shortest Paths is Often Feasible in Practice.Proc. 5th Workshop on Algorithm Engineering (WAE’01), Springer LNCS 2141, 185–197, 2001.
K. Ishikawa, M. Ogawa, S. Azume, and T. Ito. Map Navigation Software of the Electro Multivision of the’ 91 Toyota Soarer.IEEE Int. Conf. Vehicle Navig. Inform. Syst., 463–473, 1991.
R. Jakob, M. Marathe, and K. Nagel. A Computational Study of Routing Algorithms for Realistic Transportation Networks.The ACM Journal of Experimental Algorithmics, Vol. 4, Article 6, 1999.
S. Jung and S. Pramanik. HiTi Graph Model of Topographical Road Maps in Navigation Systems.Proc. 12th IEEE Int. Conf. Data Eng., 76–84, 1996.
D. Kavvadias, G. Pantziou, P. Spirakis, and C. Zaroliagis. Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problems.Theoretical Computer Science, Vol. 168, No. 1, 121–154, 1996.
T. Preuss and J.-H. Syrbe. An Integrated Traffic Information System.Proc. 6th Int. Conf. Appl. Computer Networking in Architecture, Construction, Design, Civil Eng., and Urban Planning (europIA’ 97), 1997.
S. Shekhar, A. Fetterer, and G. Goyal. Materialization trade-offs in hierarchical shortest path algorithms.Proc. Int. Symp. Large Spatial Databases, Springer LNCS 1262, 94–111, 1997.
S. Shekhar, A. Kohli, and M. Coyle. Path Computation Algorithms for Advanced Traveler Information System (ATIS).Proc. 9th IEEE Int. Conf. Data Eng., 31–39, 1993.
J. Shapiro, J. Waxman, and D. Nir. Level Graphs and Approximate Shortest Path Algorithms.Network 22, 691–717, 1992.
L. Siklóssy and E. Tulp. The Space Reduction Method: A method to reduce the size of search spaces.Information Processing Letters, 38(4), 187–192, 1991.
F. Schulz, D. Wagner, and K. Weihe. Dijkstra’s Algorithm On-Line: An Empirical Study from Public Railroad Study.ACM Journal of Experimental Algorithmics, Vol. 5, Article 12, 2000, Special issue on WAE’99.
J. D. Ullman and M. Yannakakis, High Probability Parallel Transitive Closure Algorithms,SIAM J. on Computing 20(1), pp. 100–125, 1991.
Author information
Authors and Affiliations
Department of Computer and Information Science, University of Konstanz, Box D188, 78457, Konstanz, Germany
Frank Schulz & Dorothea Wagner
Computer Technology Institute, and Department of Computer Engineering & Informatics, University of Patras, 26500, Patras, Greece
Frank Schulz & Christos Zaroliagis
- Frank Schulz
You can also search for this author inPubMed Google Scholar
- Dorothea Wagner
You can also search for this author inPubMed Google Scholar
- Christos Zaroliagis
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Department of Computer Science, University of Maryland, College Park, MD, 20742, USA
David M. Mount
Department of IEOR, Columbia University, 500W. 120 St., MC 4704, New York, NY, 10027, USA
Clifford Stein
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schulz, F., Wagner, D., Zaroliagis, C. (2002). Using Multi-level Graphs for Timetable Information in Railway Systems. In: Mount, D.M., Stein, C. (eds) Algorithm Engineering and Experiments. ALENEX 2002. Lecture Notes in Computer Science, vol 2409. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45643-0_4
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-43977-6
Online ISBN:978-3-540-45643-8
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative