{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:35:16Z","timestamp":1743057316860,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":23,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9780387968186"},{"type":"electronic","value":"9780387347707"}],"license":[{"start":{"date-parts":[[1988,1,1]],"date-time":"1988-01-01T00:00:00Z","timestamp":567993600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/bfb0040369","type":"book-chapter","created":{"date-parts":[[2006,8,2]],"date-time":"2006-08-02T20:03:50Z","timestamp":1154549030000},"page":"11-23","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast parallel and sequential algorithms for edge-coloring planar graphs"],"prefix":"10.1007","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moti","family":"Yung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1090\/S0002-9904-1976-14122-5","volume":"82","author":"K.I. Appel","year":"1976","unstructured":"K.I. Appel, W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc., vol 82, pp 711\u2013712, 1976.","journal-title":"Bull. Amer. Math. Soc."},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/0196-6774(87)90046-0","volume":"8","author":"J. Boyar","year":"1987","unstructured":"J. Boyar, H. Karloff, Coloring planar graphs in parallel, J. Algorithms 8 (1987) 470\u2013479.","journal-title":"J. Algorithms"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0196-6774(81)90031-6","volume":"2","author":"N. Chiba","year":"1981","unstructured":"N. Chiba, T. Nishizeki, N. Saito, A linear algorithm for five-coloring a planar graph, J. Algorithms 2 (1981) 317\u2013327.","journal-title":"J. Algorithms"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/0211043","volume":"11","author":"R. Cole","year":"1982","unstructured":"R. Cole, J. Hopcroft, On edge coloring bipartite graphs, SIAM J. Comput 11 (1982) 540\u2013546.","journal-title":"SIAM J. Comput"},{"key":"2_CR5","unstructured":"R.Cole, U.Vishkin, Determistic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, 18th ACM STOC (1986) 206\u2013219."},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"R.Cole, U.Vishkin, Approximate and exact parallel scheduling with applications to list, Tree and Graph Problems, 27th IEEE FOCS (1986) 478\u2013491.","DOI":"10.1109\/SFCS.1986.10"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(84)90056-5","volume":"19","author":"G.N. Frederickson","year":"1984","unstructured":"G.N. Frederickson, On linear-time algorithms for five-coloring planar graphs, Inform. Proc. Letters 19 (1984) 219\u2013224.","journal-title":"Inform. Proc. Letters"},{"key":"2_CR8","volume-title":"Edge-Colourings of Graphs","author":"S. Fiorini","year":"1977","unstructured":"S. Fiorini, R.J. Wilson, Edge-Colourings of Graphs, Pitman, London, 1977."},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0211009","volume":"11","author":"H.N. Gabow","year":"1982","unstructured":"H.N. Gabow, O. Kariv, Algorithms for edge coloring bipartite graphs and multigraphs, SIAM J. Comput. 11 (1982) 117\u2013129.","journal-title":"SIAM J. Comput."},{"key":"2_CR10","unstructured":"H.N.Gabow, T.Nishizeki, O.Kariv, D.Leven, O.Terada, Algorithms for edge-coloring graphs, TR-41\/85, Department of Computer Science, Tel Aviv University, 1985."},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"A.V.Goldberg, S.A.Plotkin, G.E.Shannon, Parallel symmetry breaking in sparse graphs, 19th ACM STOC, New York, 1987.","DOI":"10.1145\/28395.28429"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"M.Goldberg, T.Spencer, A new parallel algorithm for the maximal independent set problem, 19th IEEE FOCS, 1987.","DOI":"10.1109\/SFCS.1987.2"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"T.Hagerup, M.Chrobak, K.Diks, Optimal parallel 5-colouring of planar graphs, 14th ICALP, 1987.","DOI":"10.1007\/3-540-18088-5_25"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I.J. Holyer","year":"1981","unstructured":"I.J. Holyer, The NP-completeness of edge coloring, SIAM J. Comput 10 (1981) 718\u2013720.","journal-title":"SIAM J. Comput"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0196-6774(87)90026-5","volume":"8","author":"H. Karloff","year":"1987","unstructured":"H. Karloff, D. Shmoys, Efficient parallel algorithms for edge coloring problems, J. Algorithms 8 (1987) 39\u201352.","journal-title":"J. Algorithms"},{"key":"2_CR16","unstructured":"R.M.Karp, A.Widgerson, A fast parallel algorithm for the maximal independent set problem, 16th ACM STOC, 1987."},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"M.Luby, A simple parallel algorithm for the maximal independent set problem, 17th ACM STOC, 1985.","DOI":"10.1145\/22145.22146"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D. Leven","year":"1983","unstructured":"D. Leven, Z. Galil, NP-completeness of finding the chromatic index of regular graphs, J. Algorithms 4 (1983) 35\u201344.","journal-title":"J. Algorithms"},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","volume":"C-30","author":"G.F. Lev","year":"1981","unstructured":"G.F. Lev, N. Pippenger, L.G. Valiant, A fast parallel algorithm for routing in permutation networks, IEEE Trans. on Comput. C-30 (1981) 93\u2013100.","journal-title":"IEEE Trans. on Comput."},{"key":"2_CR20","unstructured":"D.Matula, Y.Shiloah, R.Tarjan, Two linear-time algorithms for five-coloring a planar graph, Tech. Rep. No. STAN-CS-80-830, Dep. Comp. Sci., Stanford University."},{"key":"2_CR21","first-page":"25","volume":"3","author":"V.G. Vizing","year":"1964","unstructured":"V.G. Vizing, On the estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964) 25\u201330.","journal-title":"Diskret. Analiz"},{"key":"2_CR22","first-page":"9","volume":"5","author":"V.G. Vizing","year":"1965","unstructured":"V.G. Vizing, Critical graphs with a given chromatic number, Diskret. Analiz 5 (1965) 9\u201317.","journal-title":"Diskret. Analiz"},{"issue":"1","key":"2_CR23","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1093\/comjnl\/28.1.78","volume":"28","author":"M.H. Williams","year":"1985","unstructured":"M.H. Williams, A linear algorithm for coloring planar graphs with five colors, Comput. J. 28,1 (1985) 78\u201381.","journal-title":"Comput. J."}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0040369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T15:53:29Z","timestamp":1578498809000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040369"}},"subtitle":["extended abstract"],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9780387968186","9780387347707"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/bfb0040369","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}