{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T08:47:44Z","timestamp":1672390064547},"reference-count":25,"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\/bf01759077","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"869-891","source":"Crossref","is-referenced-by-count":7,"title":["Heuristics for rapidly four-coloring large planar graphs"],"prefix":"10.1007","volume":"6","author":[{"given":"Craig A.","family":"Morgenstern","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry D.","family":"Shapiro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01759077_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K. I. Appel","year":"1977","unstructured":"K. I. Appel, W. Haken, and J. Koch. 1977. Every Planar Map is Four Colorable. Part I: Discharging.Illinois J. Math.,21, 429\u2013490.","journal-title":"Illinois J. Math."},{"key":"BF01759077_CR2","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1215\/ijm\/1256049012","volume":"21","author":"K. I. Appel","year":"1977","unstructured":"K. I. Appel, W. Haken, and J. Koch. 1977. Every Planar Map is Four Colorable. Part II: Reducibility.Illinois J. Math.,21, 491\u2013567.","journal-title":"Illinois J. Math."},{"key":"BF01759077_CR3","unstructured":"R. Archuleta and H. Shapiro. 1986. A Fast Probabilistic Algorithm for Four-Coloring Large Planar Graphs.Proc. Fall 1986 Joint Computer Conference, pp. 595\u2013600."},{"key":"BF01759077_CR4","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/jgt.3190010305","volume":"1","author":"F. R. Bernhart","year":"1977","unstructured":"F. R. Bernhart. 1977. A Digest of the Four Color Theorem.J. Graph Theory,1, 207\u2013225.","journal-title":"J. Graph Theory"},{"key":"BF01759077_CR5","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D. Br\u00e9laz","year":"1979","unstructured":"D. Br\u00e9laz. 1979. New Methods to Color Vertices of a Graph.Comm. ACM.,22, 251\u2013256.","journal-title":"Comm. ACM."},{"key":"BF01759077_CR6","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. 1981. A Linear 5-Coloring Algorithm of Planar Graphs.J. Algorithms,2, 317\u2013327.","journal-title":"J. Algorithms"},{"key":"BF01759077_CR7","first-page":"151","volume":"15","author":"F. D. J. Dunstan","year":"1976","unstructured":"F. D. J. Dunstan. 1976. Sequential Colourings of Graphs.Congr. Numer.,15, 151\u2013158.","journal-title":"Congr. Numer."},{"key":"BF01759077_CR8","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. 1984. On Linear Time Algorithms for Five-Coloring Planar Graphs.Inform. Process. Lett.,19, 219\u2013224.","journal-title":"Inform. Process. Lett."},{"key":"BF01759077_CR9","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1002\/jgt.3190010304","volume":"1","author":"W. Haken","year":"1977","unstructured":"W. Haken. 1977. An Attempt to Understand the Four Color Problem.J. Graph Theory,1, 193\u2013206.","journal-title":"J. Graph Theory"},{"key":"BF01759077_CR10","first-page":"332","volume":"24","author":"P. J. Heawood","year":"1890","unstructured":"P. J. Heawood. 1890. Map-Colour Theorems.Quart. J. Math.,24, 332\u2013338.","journal-title":"Quart. J. Math."},{"key":"BF01759077_CR11","doi-asserted-by":"crossref","first-page":"193","DOI":"10.2307\/2369235","volume":"2","author":"A. B. Kempe","year":"1879","unstructured":"A. B. Kempe, 1879. On the Geographical Problem of the Four-Colors.Amer. J. Math. 2, 193\u2013200.","journal-title":"Amer. J. Math."},{"key":"BF01759077_CR12","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1090\/S0002-9904-1935-06104-X","volume":"41","author":"I. Kittell","year":"1935","unstructured":"I. Kittell. 1935. A Group of Operations on a Partially Colored Map.Bull. Amer. Math. Soc.,41, 407\u2013413.","journal-title":"Bull. Amer. Math. Soc."},{"key":"BF01759077_CR13","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1145\/3341.3350","volume":"28","author":"M. Kubale","year":"1985","unstructured":"M. Kubale and B. Jackowski. 1985. A Generalized Implicit Enumeration for Graph-Coloring.Comm. ACM.,28, 412\u2013418.","journal-title":"Comm. ACM."},{"key":"BF01759077_CR14","doi-asserted-by":"crossref","first-page":"489","DOI":"10.6028\/jres.084.024","volume":"84","author":"F. T. Leighton","year":"1979","unstructured":"F. T. Leighton. 1979. A Graph Coloring Algorithm for Large Scheduling Problems.J. Res. Nat. Bur. Standards,84, 489\u2013506.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"BF01759077_CR15","unstructured":"G. Marble and D. W. Matula. 1972. Computational Aspects of 4-Coloring Planar Graphs. Technical Report, University of Wisconsin."},{"key":"BF01759077_CR16","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/B978-1-4832-3187-7.50015-5","volume-title":"Graph Theory and Computing","author":"D. W. Matula","year":"1972","unstructured":"D. W. Matula, G. Marble, and J. D. Isaacson. 1972. Graph Coloring Algorithms. InGraph Theory and Computing (R. C. Read, ed.), Academic Press, New York, pp. 109\u2013122."},{"key":"BF01759077_CR17","first-page":"401","volume":"33","author":"D. W. Matula","year":"1981","unstructured":"D. W. Matula, Y. Shiloach, and R. E. Tarjan. 1981. Analysis of Two Linear-Time Algorithms for Five-Coloring a Planar Graph.Congr. Numer.,33, 401.","journal-title":"Congr. Numer."},{"key":"BF01759077_CR18","series-title":"Technical Report CS88-1","volume-title":"Saturation Based Graph Coloring Algorithms","author":"C. Morgenstern","year":"1988","unstructured":"C. Morgenstern. 1988. Saturation Based Graph Coloring Algorithms. Technical Report CS88-1, University of New Mexico, Albuquerque, New Mexico."},{"key":"BF01759077_CR19","volume-title":"Doctoral Dissertation","author":"C. Morgenstern","year":"1990","unstructured":"C. Morgenstern. 1990. Algorithms for General Graph Coloring. Doctoral Dissertation, Department of Computer Science, University of New Mexico, Albuquerque, New Mexico."},{"key":"BF01759077_CR20","series-title":"Technical Report CS84-7","volume-title":"Performance of Approximation Coloring Algorithms on Maximally Planar Graphs","author":"C. Morgenstern","year":"1984","unstructured":"C. Morgenstern and H. D. Shapiro. 1984. Performance of Approximation Coloring Algorithms on Maximally Planar Graphs. Technical Report CS84-7, University of New Mexico, Albuquerque, New Mexico."},{"key":"BF01759077_CR21","unstructured":"T. Nishizeki and N. Chiba. 1988. Planar Graphs: Theory and Algorithms.Ann. Discrete Math.,32."},{"key":"BF01759077_CR22","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/358161.358171","volume":"26","author":"J. Peemoller","year":"1983","unstructured":"J. Peemoller. 1983. A Correction to Brelaz's Modification of Brown's Coloring Algorithm.Comm. ACM,26, 595\u2013597.","journal-title":"Comm. ACM"},{"key":"BF01759077_CR23","volume-title":"The Four-Color Problem","author":"T. L. Saaty","year":"1986","unstructured":"T. L. Saaty and P. C. Kainen. 1986.The Four-Color Problem. Dover, New York."},{"key":"BF01759077_CR24","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1093\/comjnl\/27.2.165","volume":"27","author":"M. H. Williams","year":"1984","unstructured":"M. H. Williams and K. T. Milne. 1984. The Performance of Algorithms for Colouring Planar Graphs.Comput. J.,27, 165\u2013170.","journal-title":"Comput. J."},{"key":"BF01759077_CR25","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/spe.4380040306","volume":"4","author":"M. R. Williams","year":"1974","unstructured":"M. R. Williams. 1974. Heuristic Procedures.Software-Practice and Experience,4, 237\u2013240.","journal-title":"Software-Practice and Experience"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759077.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759077\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:27:01Z","timestamp":1586287621000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":25,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759077"],"URL":"https:\/\/doi.org\/10.1007\/bf01759077","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}