{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T21:32:19Z","timestamp":1778535139125,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540439776","type":"print"},{"value":"9783540456438","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45643-0_4","type":"book-chapter","created":{"date-parts":[[2007,9,25]],"date-time":"2007-09-25T00:58:33Z","timestamp":1190681913000},"page":"43-59","source":"Crossref","is-referenced-by-count":54,"title":["Using Multi-level Graphs for Timetable Information in Railway Systems"],"prefix":"10.1007","author":[{"given":"Frank","family":"Schulz","sequence":"first","affiliation":[]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,7,12]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1109\/69.277767","volume":"6","author":"R. Agrawal","year":"1994","unstructured":"R. Agrawal and H. Jagadish. Algorithms for Searching Massive Graphs. IEEE Transact. Knowledge and Data Eng., Vol. 6, 225\u2013238, 1994.","journal-title":"IEEE Transact. Knowledge and Data Eng."},{"issue":"3","key":"4_CR2","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"C. Barrett","year":"2000","unstructured":"C. Barrett, R. Jacob, and M. Marathe. Formal-Language-Constrained Path Problems. SIAM Journal on Computing, Vol. 30, No. 3, 809\u2013837, 2000.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/3-540-44808-X_10","volume-title":"Proc. 3rd Workshop Algorithm Engineering and Experiments (ALENEX\u2019 01)","author":"U. Brandes","year":"2001","unstructured":"U. Brandes, F. Schulz, D. Wagner, and T. Willhalm. Travel Planning with Self-Made Maps. Proc. 3rd Workshop Algorithm Engineering and Experiments (ALENEX\u2019 01), Springer LNCS Vol. 2153, 132\u2013144, 2001."},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"A. Car and A. Frank. Modelling a Hierarchy of Space Applied to Large Road Networks. Proc. Int. Worksh. Adv. Research Geogr. Inform. Syst. (IGIS\u2019 94), 15\u201324, 1994.","DOI":"10.1007\/3-540-58795-0_30"},{"issue":"2","key":"4_CR5","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0304-3975(98)00021-8","volume":"203","author":"S. Chaudhuri","year":"1998","unstructured":"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\u2013223, 1998.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"4_CR6","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/s004530010016","volume":"27","author":"S. Chaudhuri","year":"2000","unstructured":"S. Chaudhuri and C. Zaroliagis. Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms. Algorithmica, Vol. 27, No. 3, 212\u2013226, Special Issue on Treewidth, 2000.","journal-title":"Algorithmica"},{"issue":"1","key":"4_CR7","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1145\/102782.102788","volume":"38","author":"G. Frederickson","year":"1991","unstructured":"G. Frederickson. Planar graph decomposition and all pairs shortest paths. Journal of the ACM, Vol. 38, Issue 1, 162\u2013204, 1991.","journal-title":"Journal of the ACM"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1006\/jagm.1995.1027","volume":"19","author":"G. Frederickson","year":"1995","unstructured":"G. Frederickson. Using Cellular Graph: Embeddings in Solving All Pairs Shortest Path Problems. Journal of Algorithms, Vol. 19, 45\u201385, 1995.","journal-title":"Journal of Algorithms"},{"key":"4_CR9","unstructured":"http:\/\/bahn.hafas.de . Hafas is a trademark of Hacon Ingenieurgesellschaft mbH, Hannover, Germany."},{"key":"4_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-44688-5_15","volume-title":"Proc. 5th Workshop on Algorithm Engineering (WAE\u201901)","author":"M. M\u00fcller-Hannemann","year":"2001","unstructured":"M. M\u00fcller-Hannemann and K. Weihe. Pareto Shortest Paths is Often Feasible in Practice. Proc. 5th Workshop on Algorithm Engineering (WAE\u201901), Springer LNCS 2141, 185\u2013197, 2001."},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"K. Ishikawa, M. Ogawa, S. Azume, and T. Ito. Map Navigation Software of the Electro Multivision of the\u2019 91 Toyota Soarer. IEEE Int. Conf. Vehicle Navig. Inform. Syst., 463\u2013473, 1991.","DOI":"10.4271\/912790"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/347792.347814"},{"key":"4_CR13","unstructured":"S. Jung and S. Pramanik. HiTi Graph Model of Topographical Road Maps in Navigation Systems. Proc. 12th IEEE Int. Conf. Data Eng., 76\u201384, 1996."},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0304-3975(96)00065-5","volume":"168","author":"D. Kavvadias","year":"1996","unstructured":"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\u2013154, 1996.","journal-title":"Theoretical Computer Science"},{"key":"4_CR15","unstructured":"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\u2019 97), 1997."},{"key":"4_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/3-540-63238-7_26","volume-title":"Proc. Int. Symp. Large Spatial Databases","author":"S. Shekhar","year":"1997","unstructured":"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\u2013111, 1997."},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"S. Shekhar, A. Kohli, and M. Coyle. Path Computation Algorithms for Advanced Traveler Information System (ATIS). Proc. 9th IEEE Int. Conf. Data Eng., 31\u201339, 1993.","DOI":"10.1109\/ICDE.1993.344080"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1002\/net.3230220707","volume":"22","author":"J. Shapiro","year":"1992","unstructured":"J. Shapiro, J. Waxman, and D. Nir. Level Graphs and Approximate Shortest Path Algorithms. Network 22, 691\u2013717, 1992.","journal-title":"Network"},{"issue":"4","key":"4_CR19","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0020-0190(91)90098-3","volume":"38","author":"L. Sikl\u00f3ssy","year":"1991","unstructured":"L. Sikl\u00f3ssy and E. Tulp. The Space Reduction Method: A method to reduce the size of search spaces. Information Processing Letters, 38(4), 187\u2013192, 1991.","journal-title":"Information Processing Letters"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"F. Schulz, D. Wagner, and K. Weihe. Dijkstra\u2019s Algorithm On-Line: An Empirical Study from Public Railroad Study. ACM Journal of Experimental Algorithmics, Vol. 5, Article 12, 2000, Special issue on WAE\u201999.","DOI":"10.1145\/351827.384254"},{"issue":"1","key":"4_CR21","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1137\/0220006","volume":"20","author":"J. D. Ullman","year":"1991","unstructured":"J. D. Ullman and M. Yannakakis, High Probability Parallel Transitive Closure Algorithms, SIAM J. on Computing 20(1), pp. 100\u2013125, 1991.","journal-title":"SIAM J. on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering and Experiments"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45643-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T07:53:51Z","timestamp":1556870031000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45643-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540439776","9783540456438"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45643-0_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}