{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:52Z","timestamp":1725663712303},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540538325"},{"type":"electronic","value":"9783540463108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-53832-1_27","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:13:17Z","timestamp":1330189997000},"page":"1-17","source":"Crossref","is-referenced-by-count":1,"title":["Optimal parallel algorithms for sparse graphs"],"prefix":"10.1007","author":[{"given":"Grammati E.","family":"Pantziou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","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,7]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"R.Cole, U.Viskin, \u201cApproximate and Exact Parallel Scheduling with applications to list, tree and graph problems\u201d, Proc. 27th IEEE Symp. on FOCS, 1986, pp. 478\u2013491.","DOI":"10.1109\/SFCS.1986.10"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"A.Goldberg, S.Plotkin, G.Shannon, \u201cParallel Symmetry-Breaking in Sparse Graphs\u201d, Proc. of the ACM 19th STOC (Symp. on Theory of Computing), 1987, pp. 315\u2013324.","DOI":"10.1145\/28395.28429"},{"key":"1_CR3","volume-title":"Parallel Algorithms on Planar Graphs","author":"T. Hagerup","year":"1988","unstructured":"T. Hagerup, \u201cParallel Algorithms on Planar Graphs\u201d, Ph.D. Thesis, University of Saarlandes, Saarbr\u00fccken, 1988."},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"T.Hagerup, M.Chrobak, K.Diks, \u201cParallel 5-coloring of planar graphs\u201d, Proc. of the 14th ICALP, pp. 304\u2013313, LNCS, Vol. 267, Springer-Verlag.","DOI":"10.1007\/3-540-18088-5_25"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0020-0190(88)90084-1","volume":"27","author":"H. Jung","year":"1988","unstructured":"H. Jung, K. Mehlhorn, \u201cParallel Algorithms for Computing Maximal Independent Sets in Trees and for Updating Minimum Spanning Trees\u201d, Information Processing Letters 27, pp. 227\u2013236, April 1988.","journal-title":"Information Processing Letters"},{"issue":"4","key":"1_CR6","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"A. Itai, C.H. Papadimitriou, J.L. Szwarcfiter, \u201cHamilton Paths in Grid Graphs\u201d, SIAM Jour. on Comp., Vol.11, No.4, November 1982, pp.676\u2013686.","journal-title":"SIAM Jour. on Comp."},{"key":"1_CR7","unstructured":"D.E.Knuth, \u201cThe Art of Computer Programming\u201d, Vol.1, Fundamental Algorithms, 2nd ed. Addison-Wesley, 1973."},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"P.Klein, J.H.Reif, \u201cAn Efficient Parallel Algorithm for Planarity\u201d, Proc. 27th IEEE Symp. on FOCS, 1986, pp.465\u2013477.","DOI":"10.1109\/SFCS.1986.6"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"V.Ramachandran, J.H.Reif, \u201cAn Optimal Parallel Algorithm for Graph Planarity\u201d, Proc. 30th IEEE Symp. on FOCS, 1989, pp.282\u2013287.","DOI":"10.1109\/SFCS.1989.63491"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"B.Schieber, U.Viskin, \u201cOn Finding Lowest Common Ancestors: Simplification and Parallelization\u201d, Proc. of 3rd Aegean Workshop on Computing (AWOC 88), Corfu, Greece, June\/July 1988, pp. 111\u2013123, LNCS 319, ed. J.H Reif, Spriger-Verlag.","DOI":"10.1007\/BFb0040379"},{"issue":"4","key":"1_CR11","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 Jour. on Comp., Vol.14, No.4, November 1985, pp.862\u2013874.","journal-title":"SIAM Jour. on Comp."},{"key":"1_CR12","volume-title":"The Complexity of Parallel Computation","author":"J.C. Wyllie","year":"1979","unstructured":"J.C. Wyllie, \u201cThe Complexity of Parallel Computation\u201d, Ph.D. Thesis, TR 79-387, Dept of Computer Science, Cornell Univesity, Ithaca, NY, 1979."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-53832-1_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:50:57Z","timestamp":1605628257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-53832-1_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540538325","9783540463108"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-53832-1_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}