{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:47:17Z","timestamp":1765176437199},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1007\/bf01759072","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"801-815","source":"Crossref","is-referenced-by-count":5,"title":["An efficient parallel algorithm for computing a large independent set in a planar graph"],"prefix":"10.1007","volume":"6","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01759072_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1974","unstructured":"A. Aho, J. Hopcroft, J. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"BF01759072_CR2","doi-asserted-by":"crossref","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. 82 (1976), 711\u2013712.","journal-title":"Bull Amer. Math. Soc."},{"key":"BF01759072_CR3","doi-asserted-by":"crossref","unstructured":"B. S. Baker, Approximation algorithms for NP-complete problems on planar graphs,Proc. 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 265\u2013273.","DOI":"10.1109\/SFCS.1983.7"},{"key":"BF01759072_CR4","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"C. Berge,Graphs and Hypergraphs, North-Holland, Amsterdam, 1973."},{"key":"BF01759072_CR5","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, N. Saito, A linear algorithm for five-coloring a planar graph,J. Algorithms 2 (1981), 317\u2013327.","journal-title":"J. Algorithms"},{"key":"BF01759072_CR6","doi-asserted-by":"crossref","unstructured":"N. Chiba, T. Nishizeki, N. Saito, An approximation algorithm for the maximum independent set problem on planar graphs,SIAM. J. Comput. (1982), 663\u2013675.","DOI":"10.1137\/0211055"},{"key":"BF01759072_CR7","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, On linear-time algorithms for five-coloring planar graphs,Inform. Process. Lett. 19 (1984), 219\u2013224.","journal-title":"Inform. Process. Lett."},{"key":"BF01759072_CR8","volume-title":"Computers and Intractability-a Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey, D. S. Johnson,Computers and Intractability-a Guide to the Theory of NP-completeness, Freeman, New York, 1979."},{"key":"BF01759072_CR9","doi-asserted-by":"crossref","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, L. Stockmayer, Some simplified NP-complete problems,Theoret. Comput. Sci. 1 (1976), 237\u2013267.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01759072_CR10","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"A. Goldberg","year":"1988","unstructured":"A. Goldberg, S. Poltkin, G. Shannon, Parallel symmetry breaking in sparse graphs,SIAM J. Discrete Math. 1 (1988), 434\u2013446.","journal-title":"SIAM J. Discrete Math."},{"key":"BF01759072_CR11","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1137\/0218020","volume":"18","author":"T. Hagerup","year":"1989","unstructured":"T. Hagerup, M. Chrobak, K. Diks, Optimal parallel 5-colouring of planar graphs,SIAM J. Comput. 18 (1989), 288\u2013300.","journal-title":"SIAM J. Comput."},{"key":"BF01759072_CR12","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. E. Hopcroft","year":"1974","unstructured":"J. E. Hopcroft, R. E. Tarjan, Efficient planarity testing,J. Assoc. Comput. Mach. 21 (1974), 549\u2013568.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01759072_CR13","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R. J. Lipton, R. E. Tarjan, Applications of a planar separator theorem,SIAM J. Comput. 9 (1980), 615\u2013627.","journal-title":"SIAM J. Comput."},{"key":"BF01759072_CR14","unstructured":"D. Matula, Y. Shiloah, R. Tarjan, Two linear-time algorithms for five-coloring a planar graph, Technical Report No. STAN-CS-80-830, Department of Computer Science, Stanford University."},{"key":"BF01759072_CR15","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0020-0190(87)90092-5","volume":"25","author":"J. Naor","year":"1987","unstructured":"J. Naor, A fast parallel coloring of planar graphs with five colors,Inform. Process. Lett. 25 (1987), 51\u201353.","journal-title":"Inform. Process. Lett."},{"key":"BF01759072_CR16","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, M. Yannakakis, Worst-case ratios for planar graphs and the method of induction on faces,Proc. 22nd IEEE Symp. on Foundations of Computer Science, 1981, pp. 358\u2013363.","DOI":"10.1109\/SFCS.1981.55"},{"key":"BF01759072_CR17","doi-asserted-by":"crossref","unstructured":"V. Ramachandran, J. Reif, An optimal parallel algorithm for graph planarity,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 282\u2013287.","DOI":"10.1109\/SFCS.1989.63491"},{"key":"BF01759072_CR18","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1002\/sapm1949281148","volume":"28","author":"C.E. Shannon","year":"1949","unstructured":"C.E. Shannon, A theorem on colouring lines of a network,J. Math. Phys. 28(1949), 148\u2013151.","journal-title":"J. Math. Phys."},{"issue":"1","key":"BF01759072_CR19","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, A linear algorithm for coloring planar graphs with five colors,Comput. J. 28(1) (1985), 78\u201381.","journal-title":"Comput. J."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759072.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759072\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:27:09Z","timestamp":1586287629000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":19,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759072"],"URL":"https:\/\/doi.org\/10.1007\/bf01759072","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}