{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:43Z","timestamp":1725663523485},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540180883"},{"type":"electronic","value":"9783540477471"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18088-5_25","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:26:27Z","timestamp":1330179987000},"page":"304-313","source":"Crossref","is-referenced-by-count":6,"title":["Parallel 5-colouring of planar graphs"],"prefix":"10.1007","author":[{"given":"Torben","family":"Hagerup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krzysztof","family":"Diks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"M. J. Atallah and M. T. Goodrich: \u201cEfficient Plane Sweeping in Parallel\u201d. Proceedings, 2nd Annual Symposium on Computational Geometry (1986), 216\u2013225.","DOI":"10.1145\/10515.10539"},{"key":"25_CR2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K. Appel","year":"1977","unstructured":"K. Appel and W. Haken: \u201cEvery Planar Map is Four Colorable. Part I: Discharging\u201d. Illinois Journal of Mathematics 21 (1977), 429\u2013490.","journal-title":"Illinois Journal of Mathematics"},{"key":"25_CR3","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1215\/ijm\/1256049012","volume":"21","author":"K. Appel","year":"1977","unstructured":"K. Appel, W. Haken, and J. Koch: \u201cEvery Planar Map is Four Colorable. Part II: Reducibility\u201d. Illinois Journal of Mathematics 21 (1977), 491\u2013567.","journal-title":"Illinois Journal of Mathematics"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di: \u201cAn O(n log n) Sorting Network\u201d. Proceedings, 15th Annual ACM Symposium on Theory on Computing (1983), 1\u20139.","DOI":"10.1145\/800061.808726"},{"key":"25_CR5","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"B. Bollob\u00e1s: \u201cExtremal Graph Theory\u201d. Academic Press, London, 1978."},{"key":"25_CR6","first-page":"28","volume":"199","author":"F. Bauern\u00f6ppel","year":"1985","unstructured":"F. Bauern\u00f6ppel and H. Jung: \u201cFast Parallel Vertex Colouring\u201d. Proceedings, International Conference on Fundamentals of Computation Theory (1985), LNCS 199, 28\u201335.","journal-title":"LNCS"},{"key":"25_CR7","unstructured":"J. Boyar and H. Karloff: \u201cColoring Planar Graphs in Parallel\u201d. To appear in Journal of Algorithms."},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"R. Cole: \u201cParallel Merge Sort\u201d. 27th Annual Symposium on Foundations of Computer Science (1986), 511\u2013516.","DOI":"10.1109\/SFCS.1986.41"},{"key":"25_CR9","unstructured":"M. Chrobak and K. Diks: \u201cTwo Algorithms for Coloring Planar Graphs with 5 Colors\u201d. Technical Report, Columbia University, January 1987."},{"issue":"4","key":"25_CR10","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0196-6774(81)90031-6","volume":"2","author":"N. Chiba","year":"1981","unstructured":"N. Chiba, T. Nishizeki, and N. Saito: \u201cA Linear 5-Coloring Algorithm of Planar Graphs\u201d. Journal of Algorithms 2:4 (1981), 317\u2013327.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"25_CR11","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"R. Cole and U. Vishkin: \u201cDeterministic Coin Tossing with Applications to Optimal Parallel List Ranking\u201d. Information and Control 70:1 (1986), 32\u201353.","journal-title":"Information and Control"},{"key":"25_CR12","first-page":"273","volume":"233","author":"K. Diks","year":"1986","unstructured":"K. Diks: \u201cA Fast Parallel Algorithm for Six-Colouring of Planar Graphs\u201d. Proceedings, 12th Symposium on Mathematical Foundations of Computer Science (1986), LNCS 233, 273\u2013282.","journal-title":"LNCS"},{"key":"25_CR13","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"S. Even: \u201cGraph Algorithms\u201d. Pitman, London, 1979."},{"issue":"5","key":"25_CR14","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(84)90056-5","volume":"19","author":"G. N. Frederickson","year":"1984","unstructured":"G. N. Frederickson: \u201cOn Linear-Time Algorithms for Five-Coloring Planar Graphs\u201d. Information Processing Letters 19:5 (1984), 219\u2013224.","journal-title":"Information Processing Letters"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, and L. Stockmeyer: \u201cSome Simplified N P-Complete Graph Problems\u201d. Theoretical Computer Science 1 (1976), 237\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, S. A. Plotkin, and G. E. Shannon: \u201cParallel Symmetry-Breaking in Sparse Graphs\u201d. Proceedings, 19th Annual ACM Symposium on Theory of Computing (1987).","DOI":"10.1145\/28395.28429"},{"key":"25_CR17","unstructured":"T. Hagerup: \u201cParallel 5-Colouring of Planar Graphs\u201d. Technical Report 10\/1986, Universit\u00e4t des Saarlandes, November 1986."},{"issue":"1","key":"25_CR18","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"D. Kirkpatrick: \u201cOptimal Search in Planar Subdivisions\u201d. SIAM Journal on Computing 12:1 (1983), 28\u201335.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"25_CR19","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0020-0190(78)90065-0","volume":"7","author":"R. J. Lipton","year":"1978","unstructured":"R. J. Lipton and R. E. Miller: \u201cA Batching Method for Coloring Planar Graphs\u201d. Information Processing Letters 7:4 (1978), 185\u2013188.","journal-title":"Information Processing Letters"},{"key":"25_CR20","unstructured":"J. Naor: \u201cA Fast Parallel Coloring of Planar Graphs with Five Colors\u201d. To appear in Information Processing Letters."},{"issue":"1","key":"25_CR21","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1093\/comjnl\/28.1.78","volume":"28","author":"M. H. Williams","year":"1985","unstructured":"M. H. Williams: \u201cA Linear Algorithm for Colouring Planar Graphs with Five Colours\u201d. The Computer Journal 28:1 (1985), 78\u201381.","journal-title":"The Computer Journal"}],"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-18088-5_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:14:04Z","timestamp":1605626044000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18088-5_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540180883","9783540477471"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-18088-5_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}