{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:11:12Z","timestamp":1725664272913},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540603139"},{"type":"electronic","value":"9783540449133"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60313-1_132","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:17:28Z","timestamp":1330262248000},"page":"31-45","source":"Crossref","is-referenced-by-count":3,"title":["Optimal parallel shortest paths in small treewidth digraphs"],"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,1]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BF01459088","volume":"99","author":"W. Ackermann","year":"1928","unstructured":"W. Ackermann, \u201cZum Hilbertschen Aufbau der reellen Zahlen\u201d, Math. Ann., 99(1928), pp.118\u2013133.","journal-title":"Math. Ann."},{"key":"3_CR2","unstructured":"A. Aho, J. Hopcroft and J. Ullman, \u201cThe Design and Analysis of Computer Algorithms\u201d, Addison-Wesley, 1974."},{"key":"3_CR3","unstructured":"R. Ahuja, T. Magnanti and J. Orlin, \u201cNetwork Flows\u201d, Prentice-Hall, 1993."},{"key":"3_CR4","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":"3_CR5","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 (1985), pp.2\u201323.","journal-title":"BIT"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, \u201cNC-algorithms for Graphs with Small Treewidth\u201d, Proc. 14th WG'88, LNCS 344, Springer-Verlag, pp.1\u201310, 1989.","DOI":"10.1007\/3-540-50728-0_32"},{"issue":"No.1\u20132","key":"3_CR7","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":"3_CR8","doi-asserted-by":"crossref","unstructured":"H. Bodlaender and T. Hagerup, \u201cParallel Algorithms with Optimal Speedup for Bounded Treewidth\u201d, Proc. 22nd ICALP'95, LNCS, Springer-Verlag, to appear.","DOI":"10.1007\/3-540-60084-1_80"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"S. Chaudhuri and C. Zaroliagis, \u201cShortest Path Queries in Digraphs of Small Treewidth\u201d, Proc. 22nd ICALP'95, LNCS, Springer-Verlag, to appear.","DOI":"10.1007\/3-540-60084-1_78"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"E. Cohen, \u201cEfficient Parallel Shortest-paths in Digraphs with a Separator Decomposition\u201d, Proc. 5th ACM SPAA, 1993, pp.57\u201367.","DOI":"10.1145\/165231.165240"},{"key":"3_CR11","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'95, LNCS 900, pp. 193\u2013204, Springer-Verlag, 1995.","DOI":"10.1007\/3-540-59042-0_73"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Y. Han, V. Pan and J. Reif, \u201cEfficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs\u201d, Proc. 4th ACM SPAA, 1992, pp.353\u2013362.","DOI":"10.1145\/140901.141913"},{"key":"3_CR13","unstructured":"J. J\u00e1J\u00e1, \u201cAn Introduction to Parallel Algorithms\u201d, Addison-Wesley, 1992."},{"key":"3_CR14","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":"3_CR15","doi-asserted-by":"crossref","unstructured":"P. Klein and S. Subramanian, \u201cA linear-processor polylog-time algorithm for shortest paths in planar graphs\u201d, Proc. 34th IEEE Symp. on FOCS, 1993, pp.259\u2013270.","DOI":"10.1109\/SFCS.1993.366861"},{"key":"3_CR16","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"N. Robertson and P. Seymour, \u201cGraph Minors I: Excluding a Forest\u201d, J. Comb. Theory Series B, 35 (1983), pp.39\u201361.","journal-title":"J. Comb. Theory Series B"},{"key":"3_CR17","doi-asserted-by":"publisher","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"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"R.E. Tarjan, \u201cData Structures and Network Algorithms\u201d, SIAM, 1983.","DOI":"10.1137\/1.9781611970265"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60313-1_132.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:37:00Z","timestamp":1619559420000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60313-1_132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540603139","9783540449133"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-60313-1_132","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}