{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:16:25Z","timestamp":1765887385045},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_145","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:38:04Z","timestamp":1330209484000},"page":"327-338","source":"Crossref","is-referenced-by-count":18,"title":["Computing shortest paths and distances in planar graphs"],"prefix":"10.1007","author":[{"given":"Hristo N.","family":"Djidjev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grammati E.","family":"Pantziou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos D.","family":"Zaroliagis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"G. Ausiello, G.F. Italiano, A.M. Spaccamela, U. Nanni, \u201cIncremental algorithms for minimal length paths\u201d, Proc. of ACM-SIAM SODA, 1990, pp.12\u201321.","DOI":"10.1016\/0196-6774(91)90036-X"},{"issue":"1","key":"25_CR2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1137\/0217004","volume":"17","author":"D. Beinstock","year":"1988","unstructured":"D. Beinstock, C.L. Monma, \u201cOn the complexity of covering faces by vertices in a planar graph\u201d, SIAM J. Comp., Vol.17, No.1, Feb. 1988, pp.53\u201376.","journal-title":"SIAM J. Comp."},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"B. Berger, J. Rompel, P.W. Shor, \u201cEfficient NC-algorithms for set cover with applications to learning and geometry\u201d, Proc. 30th IEEE Symp. on FOCS, 1989, pp.54\u201359.","DOI":"10.1109\/SFCS.1989.63455"},{"key":"25_CR4","volume-title":"Computing Shortest Paths and Distances in Planar Graphs","author":"H. Djidjev","year":"1990","unstructured":"H. Djidjev, G. Pantziou, C. Zaroliagis, \u201cComputing Shortest Paths and Distances in Planar Graphs\u201d, CTI TR-90.10.26, Computer Technology Institute, Patras, October 1990."},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"G.N. Frederickson, \u201cFast Algorithms for Shortest Paths in Planar Graphs with Applications\u201d, SIAM J. Comp., Vol.16, 1987, pp.1004\u20131022.","journal-title":"SIAM J. Comp."},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \u201cPlanar Graph Decomposition and All Pairs Shortest Paths\u201d, TR-89-015, ICSI, Berkeley, March 1989. A preliminary version was appeared as \u201cA new approach to all pairs shortest paths in planar graphs\u201d, Proc. 19th ACM STOC, New York City, May 1987, pp.19\u201328.","DOI":"10.1145\/28395.28398"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson \u201cUsing Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems\u201d, CSD-TR-897, Purdue University, August 1989. A preliminary version was appeared in Proc. 30th IEEE Symp. on FOCS, 1989, pp.448\u2013453.","DOI":"10.1109\/SFCS.1989.63517"},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01762113","volume":"3","author":"G.N. Frederickson","year":"1988","unstructured":"G.N. Frederickson, R. Janardan, \u201cDesigning Networks with Compact Routing Tables\u201d, Algorithmica, 3 (1988), pp.171\u2013190.","journal-title":"Algorithmica"},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"M.L. Fredman, R.E. Tarjan, \u201cFibonacci heaps and their use in improved network optimization algorithms\u201d, J. ACM, 34(1987), pp.596\u2013615.","journal-title":"J. ACM"},{"key":"25_CR10","unstructured":"D. Knuth, \u201cThe Art of Computer Programming\u201d, Vol.1, Fundamental Algorithms, 2nd ed. Addison-Wesley, 1973."},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"A. Lingas, \u201cEfficient parallel algorithms for path problems in planar directed graphs\u201d, Proc. of SIGAL90, LNCS, Vol.450, pp. 447\u2013457.","DOI":"10.1007\/3-540-52921-7_94"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"G. Pantziou, P. Spirakis, C. Zaroliagis, \u201cEfficient Parallel Algorithms for Shortest Paths in Planar Graphs\u201d, CTI TR-90.01.02, Computer Technology Institute, Patras, September 1990 (revised version). A preliminary version has appeared as Proc. of the 2nd Scand. Workshop on Algorithm Theory (SWAT90), Bergen, Norway, 11\u201314 July, 1990, LNCS, Vol. 447, pp.288\u2013300, Springer-Verlag.","DOI":"10.1007\/3-540-52846-6_98"},{"key":"25_CR13","first-page":"111","volume":"319","author":"B. Schieber","year":"1988","unstructured":"B. Schieber, U. Vishkin, \u201cOn finding lowest common ancestors: simplification and parallelization\u201d, Proc. 3rd AWOC88, Corfu, Greece, July 1988, LNCS Vol. 319 (ed. J.H. Reif), pp.111\u2013123, Springer-Verlag.","journal-title":"LNCS"},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan, U. Vishkin, \u201cAn efficient parallel biconnectivity algorithm\u201d, SIAM J. Comp., 14 (1985), pp. 862\u2013874.","journal-title":"SIAM J. Comp."},{"key":"25_CR15","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-642-95486-3_22","volume-title":"The Book of L","author":"J. Leeuwen van","year":"1986","unstructured":"J. van Leeuwen, R.B. Tan, \u201cComputer Networks with compact routing tables\u201d, in The Book of L, G. Rozenberg and A. Salomaa (eds.), Springer-Verlag, New York (1986), pp.259\u2013273."},{"key":"25_CR16","volume-title":"The Complexity of Parallel Computation","author":"J.C. Wyllie","year":"1979","unstructured":"J.C. Wyllie, \u201cThe Complexity of Parallel Computation\u201d, PhD Thesis, TR 79-387, Dept of Computer Science, Cornell University, Ithaca, NY, 1979."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_145.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T03:41:47Z","timestamp":1640922107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_145","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}