{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:38Z","timestamp":1725663158138},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540186250"},{"type":"electronic","value":"9783540480334"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18625-5_52","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:40:00Z","timestamp":1330198800000},"page":"207-225","source":"Crossref","is-referenced-by-count":0,"title":["Parallel algorithms for approximate edge colouring of simple graphs"],"prefix":"10.1007","author":[{"given":"O. A.","family":"Ogunyode","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/0022-0000(84)90003-5","volume":"29","author":"M. Atallah","year":"1984","unstructured":"M. Atallah and U. Vishkin, \"Finding Euler Tours in Parallel\", J. Comput. and Syst. Sciences\n29, 330\u2013337 (1984).","journal-title":"J. Comput. and Syst. Sciences"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1093\/comjnl\/24.1.85","volume":"24","author":"R. D. Dutton","year":"1981","unstructured":"R.D. Dutton and R.C. Brigham, \"A new graph colouring algorithm\", Computer J.\n24, 85\u201386 (1981).","journal-title":"Computer J."},{"key":"16_CR3","unstructured":"A.M. Frieze, \"Parallel Algorithms for Finding Hamiltonian Cycles in Random Graphs\", Manuscript, Department of Computer Science, Queen Mary College (March 1986)."},{"key":"16_CR4","unstructured":"M.R. Garey and D.S. Johnson, \"Computer and Intractability: A Guide to the Theory of NP-completeness\", Freeman (1979)."},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0211009","volume":"11","author":"H. N. Grabow","year":"1982","unstructured":"H.N. Grabow and O. Kariv, \"Algorithms for Edge Colouring Bipartite Graphs and Multigraphs\", SIAM J. Comput.\n11, 117\u2013129 (1982).","journal-title":"SIAM J. Comput."},{"key":"16_CR6","unstructured":"A.M. Gibbons, \"Algorithmic Graph Theory\", Cambridge University Press (1985)."},{"key":"16_CR7","unstructured":"A.M. Gibbons and O.A. Ogunyode, \"A Polynomial-Time Algorithm to Edge-Colour Almost All Graphs Using \u03c6e Colours\", Theory of Computation, Report No.\n68, (September 1984)."},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"I. Holyer, \"The NP-completeness of Edge-Colouring\", SIAM J. Comput.\n10, 718\u2013720 (1981).","journal-title":"SIAM J. Comput."},{"key":"16_CR9","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, \"A graph coloring algorithm for large scheduling problems\", J. Res. Natn. Bur. Stand.\n84, 489\u2013506 (1979).","journal-title":"J. Res. Natn. Bur. Stand."},{"key":"16_CR10","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","volume":"C-30","author":"G. Lev","year":"1981","unstructured":"G. Lev, N. Pippenger and L.G. Valliant, \"A Fast Parallel Algorithm for Routing in Permutation Networks\", IEEE Trans. Comput., C-30, 93\u2013110 (1981).","journal-title":"IEEE Trans. Comput."},{"key":"16_CR11","unstructured":"O.A. Ogunyode, \"Approximation and Parallel Algorithms for Some NP-Hard Problems\", Ph.D. Thesis, Department of Computer Science, University of Warwick (August 1986)."},{"key":"16_CR12","volume-title":"\"A Parallel Approximate Algorithm for the Euclidean Traveling Salesman Problem\", Report CS-83-105","author":"M. J. Quinn","year":"1983","unstructured":"M.J. Quinn and N. Deo, \"A Parallel Approximate Algorithm for the Euclidean Traveling Salesman Problem\", Report CS-83-105, Computer Science Department, Washington State University, Pullman (1983)."},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1137\/0213036","volume":"13","author":"Y. H. Tsin","year":"1984","unstructured":"Y.H. Tsin and F.Y. Chin, \"Efficient Parallel Algorithms for a Class of Graph Theoretic Problems\", SIAM J. Comput.\n13, 580\u2013599 (1984).","journal-title":"SIAM J. Comput."},{"key":"16_CR14","first-page":"25","volume":"3","author":"V. G. Vizing","year":"1964","unstructured":"V.G. Vizing, \"On an estimate of the chromatic class of p-graph\", Diskret. Analiz.\n3, 25\u201330 (1964).","journal-title":"Diskret. Analiz."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18625-5_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:15:48Z","timestamp":1619558148000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18625-5_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540186250","9783540480334"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-18625-5_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}