{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:17Z","timestamp":1750307837082,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SA 933\/1-2"],"award-info":[{"award-number":["SA 933\/1-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:p>The edge coloring problem considers the assignment of colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. We give polynomial time algorithms for approximate edge coloring of multigraphs, that is, parallel edges are allowed. The best previous algorithms achieve a fixed constant approximation factor plus a small additive offset. One of our algorithms achieves solution quality opt + \u221a9opt\/2 and has execution time polynomial in the number of nodes and the logarithm of the maximum edge multiplicity.<\/jats:p>","DOI":"10.1145\/1361192.1361198","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T15:11:43Z","timestamp":1212505903000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["An asymptotic approximation scheme for multigraph edge coloring"],"prefix":"10.1145","volume":"4","author":[{"given":"Peter","family":"Sanders","sequence":"first","affiliation":[{"name":"University of Karlsruhe"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Computer Science"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00138-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170002"},{"volume":"2462","volume-title":"Lecture Notes in Computer Science","author":"Feige U.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","unstructured":"Gabow H. N. Nishizeki T. Kariv O. Leven D. and Terada O. 1985. Algorithms for edge-coloring graphs. Tech. rep. TR-41\/85 Department of Computer Science Tel Aviv University.  Gabow H. N. Nishizeki T. Kariv O. Leven D. and Terada O. 1985. Algorithms for edge-coloring graphs. Tech. rep. TR-41\/85 Department of Computer Science Tel Aviv University."},{"key":"e_1_2_1_5_1","first-page":"3","article-title":"On multigraphs of almost maximal chromatic class (in Russian)","volume":"23","author":"Goldberg M. K.","year":"1973","journal-title":"Diskret Analiz"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90039-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0067"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403035"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591725"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00356-2"},{"volume-title":"34th Southeastern International Conference on Combinatorics, Graph Theory, and Computing","year":"2003","author":"Plantholt M.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","unstructured":"Seymour P. D. 1979. Some unsolved problems on one-factorization of graphs. In Graph Theory and Related Topics J. A. Bondy and U. S. R. Murty Eds. Academic Press 367--368.  Seymour P. D. 1979. Some unsolved problems on one-factorization of graphs. In Graph Theory and Related Topics J. A. Bondy and U. S. R. Murty Eds. Academic Press 367--368."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1949281148"},{"key":"e_1_2_1_15_1","first-page":"23","article-title":"On an estimate of the chromatic class of a p-graph (in Russian)","volume":"3","author":"Vizing V. G.","year":"1964","journal-title":"Diskret. Analiz"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1361192.1361198","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1361192.1361198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:58:02Z","timestamp":1750255082000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1361192.1361198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["10.1145\/1361192.1361198"],"URL":"https:\/\/doi.org\/10.1145\/1361192.1361198","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,5]]},"assertion":[{"value":"2005-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2006-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}