{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:52Z","timestamp":1725664192259},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600848"},{"type":"electronic","value":"9783540494256"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60084-1_78","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:37:44Z","timestamp":1330277864000},"page":"244-255","source":"Crossref","is-referenced-by-count":12,"title":["Shortest path queries in digraphs of small treewidth"],"prefix":"10.1007","author":[{"given":"Shiva","family":"Chaudhuri","sequence":"first","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,7]]},"reference":[{"key":"21_CR1","unstructured":"R. Ahuja, T. Magnanti and J. Orlin, \u201cNetwork Flows\u201d, Prentice-Hall, 1993."},{"key":"21_CR2","unstructured":"N. Alon and B. Schieber, \u201cOptimal Preprocessing for Answering On-line Product Queries\u201d, Tech. Rep. No. 71\/87, Tel-Aviv University, 1987."},{"key":"21_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg, \u201cEfficient Algorithms for Combinatorial Problems on Graphs with Bounded Decomposability \u2014 A Survey\u201d, BIT, 25, pp.2\u201323, 1985.","journal-title":"BIT"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, \u201cA Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth\u201d, Proc. 25th ACM STOC, pp.226\u2013234, 1993.","DOI":"10.1145\/167088.167161"},{"issue":"No.1\u20132","key":"21_CR5","first-page":"1","volume":"11","author":"H. Bodlaender","year":"1993","unstructured":"H. Bodlaender, \u201cA Tourist Guide through Treewidth\u201d, Acta Cybernetica, Vol.11, No.1\u20132, pp.1\u201321, 1993.","journal-title":"Acta Cybernetica"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, \u201cDynamic Algorithms for Graphs with Treewidth 2\u201d, Proc. 19th WG'93, LNCS 790, pp.112\u2013124, Springer-Verlag, 1994.","DOI":"10.1007\/3-540-57899-4_45"},{"key":"21_CR7","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF01840366","volume":"2","author":"B. Chazelle","year":"1987","unstructured":"B. Chazelle, \u201cComputing on a Free Tree via Complexity-Preserving Mappings\u201d, Algorithmica, 2, pp.337\u2013361, 1987.","journal-title":"Algorithmica"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"H. Djidjev, G. Pantziou and C. Zaroliagis, \u201cOn-line and Dynamic Algorithms for Shortest Path Problems\u201d, Proc. 12th STACS, 1995, LNCS 900, pp.193\u2013204, Springer-Verlag.","DOI":"10.1007\/3-540-59042-0_73"},{"key":"21_CR9","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0304-3975(93)90328-Q","volume":"116","author":"E. Feuerstein","year":"1993","unstructured":"E. Feuerstein and A.M. Spaccamela, \u201cDynamic Algorithms for Shortest Paths in Planar Graphs\u201d, Theor. Computer Science, 116 (1993), pp.359\u2013371.","journal-title":"Theor. Computer Science"},{"key":"21_CR10","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. on Computing, 16 (1987), pp.1004\u20131022.","journal-title":"SIAM J. on Computing"},{"key":"21_CR11","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1145\/102782.102788","volume":"38","author":"G.N. Frederickson","year":"1991","unstructured":"G.N. Frederickson, \u201cPlanar Graph Decomposition and All Pairs Shortest Paths\u201d, J. ACM, 38(1991), pp.162\u2013204.","journal-title":"J. ACM"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \u201cSearching among Intervals and Compact Routing Tables\u201d, Proc. 20th ICALP, 1993, LNCS 700, pp.28\u201339, Springer-Verlag.","DOI":"10.1007\/3-540-56939-1_59"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \u201cUsing Cellular Graph Embeddings in Solving All Pairs Shortest Path Problems\u201d, accepted in J. of Algorithms, 1994.","DOI":"10.1006\/jagm.1995.1027"},{"key":"21_CR14","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. Fredman","year":"1987","unstructured":"M. Fredman and R. Tarjan, \u201cFibonacci heaps and their uses in improved network optimization algorithms\u201d, J. ACM, 34(1987), pp. 596\u2013615.","journal-title":"J. ACM"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"D. Kavvadias, G. Pantziou, P. Spirakis and C. Zaroliagis, \u201cEfficient Sequential and Parallel Algorithms for the Negative Cycle Problem\u201d, Proc. 5th ISAAC, 1994, LNCS 834, pp.270\u2013278, Springer-Verlag.","DOI":"10.1007\/3-540-58325-4_190"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Rao, M. Rauch and S. Subramanian, \u201cFaster shortest-path algorithms for planar graphs\u201d, Proc. 26th ACM STOC, 1994, pp.27\u201337.","DOI":"10.1145\/195058.195092"},{"key":"21_CR17","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. Seymour, \u201cGraph Minors II: Algorithmic Aspects of Treewidth\u201d, J. Algorithms, 7(1986), pp.309\u2013322.","journal-title":"J. Algorithms"}],"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-60084-1_78.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:54:43Z","timestamp":1605646483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60084-1_78"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600848","9783540494256"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-60084-1_78","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}