{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T05:27:37Z","timestamp":1746077257212},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441861"},{"type":"electronic","value":"9783540457534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45753-4_11","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T07:37:09Z","timestamp":1187249829000},"page":"108-121","source":"Crossref","is-referenced-by-count":30,"title":["Approximating Maximum Edge Coloring in Multigraphs"],"prefix":"10.1007","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[]},{"given":"Eran","family":"Ofek","sequence":"additional","affiliation":[]},{"given":"Udi","family":"Wieder","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.7146\/math.scand.a-11685","volume":"40","author":"L. D. Andersen","year":"1977","unstructured":"L. D. Andersen: On edge-colourings of graphs. Math. Scand. 40:161\u2013175, 1977.","journal-title":"Math. Scand."},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0020-0190(98)00138-0","volume":"68","author":"A. Caprara","year":"1998","unstructured":"Alberto Caprara and Romeo Rizzi: Improving a Family of Approximation Algorithms to Edge Color Multigraphs. Information Processing Letters, 68:11\u201315, 1998.","journal-title":"Information Processing Letters"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"R. Cole and K. Ost and S. Schirra: Edge-coloring Bipartite Multigraphs in O(E log D) Time. Combinatorica, 21(1), 2001.","DOI":"10.1007\/s004930170002"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0012-365X(80)90002-3","volume":"29","author":"G. Cornuejols","year":"1980","unstructured":"Gerard Cornuejols and William Pulleyblank: A matching Problem with Side Conditions. Discrete Mathematics, 29:135\u2013159,1980.","journal-title":"Discrete Mathematics"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Reinhard Diestel: Graph Theory. Springer 1996.","DOI":"10.1007\/978-3-662-07551-7"},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds: Maximum matching and a polyhedron with 0, 1 vertices. Journal of Research National Bureau of Standards, 69B:125\u2013130, 1965.","journal-title":"Journal of Research National Bureau of Standards"},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds: Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449\u2013467, 1965.","journal-title":"Canadian Journal of Mathematics"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Lene M. Favrholdt and Morten N. Nielsen: On-Line Edge-Coloring with a Fixed Number of Colors. Foundations of Software Technology and Theoretical Computer Science 20, 2000.","DOI":"10.1007\/3-540-44450-5_8"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"U. Feige and E. Ofek and U. Wieder: Approximating maximum edge coloring in multigraphs. Technical report, Weizmann Institute, 2002.","DOI":"10.1007\/3-540-45753-4_11"},{"key":"11_CR10","unstructured":"M.K. Goldberg: On multigraphs of almost maximal choratic class (in Russion). Diskret. Analiz, 1973."},{"key":"11_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Grotschel","year":"1988","unstructured":"M. Grotschel and L. Lovasz and A. Schrijver: Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin, 1988."},{"key":"11_CR12","unstructured":"D. Hartvigsen: Extensions of Matching Theory. Carnegie-Mellon University, 1984."},{"key":"11_CR13","volume-title":"Approximation Algorithms For NP-Hard Problems","author":"D. Hochbaum","year":"1997","unstructured":"Dorit Hochbaum: Approximation Algorithms For NP-Hard Problems. PWS Publishing Company, Boston, 1997."},{"issue":"4","key":"11_CR14","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Ian Holyer: The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718\u2013720, 1981.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"J. Kahn: Asymptotics of the Chromatic Index for Multigraphs. Journal of Combinatorial Theory, Series B, 68, 1996.","DOI":"10.1006\/jctb.1996.0067"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D. Leven","year":"1983","unstructured":"Daniel Leven and Zvi Galil: NP Completeness of Finding the Chromatic Index of Regular Graphs. Journal of Algorithms, 4(1):35\u201344, 1983.","journal-title":"Journal of Algorithms"},{"key":"11_CR17","unstructured":"L. Lovasz and Plummer:Matching Theory, Annals of Discrete Mathematics 29 North-Holland, 1986."},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1137\/0403035","volume":"3","author":"T. Nishizeki","year":"1990","unstructured":"Takao Nishizeki and Kenichi Kashiwagi: On the 1.1 Edge-Coloring of Multigraphs. SIAM Journal on Discrete Mathematics 3:391\u2013410, 1990.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"T. Nishizeki and X. Zhou: Edge-Coloring and f-coloring for various classes of graphs. Journal of Graph Algorithms and Applications, 3, 1999.","DOI":"10.7155\/jgaa.00012"},{"key":"11_CR20","unstructured":"Eran Ofek: Maximum edge coloring with a bounded number of colors. Weizmann Institute of Science, Rehovot, Israel, November 2001."},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"M. Padberg","year":"1982","unstructured":"M. Padberg and M. R. Rao: Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 1982, 7:67\u201380.","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"11_CR22","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"Christos H. Papadimitriou and Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences, 43(3):425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR23","unstructured":"P. Seymour: Some unsolved problems on one-factorizations of graphs. Graph Theory and Related Topics, Academic Press, 367\u2013368, 1979."},{"key":"11_CR24","first-page":"23","volume":"3","author":"V. G. Vizing","year":"1964","unstructured":"V. G. Vizing: On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz 3:23\u201330, 1964.","journal-title":"On an estimate of the chromatic class of a p-graph"},{"key":"11_CR25","unstructured":"Ehud Wieder: Offine satellite resource allocation or Maximum edge coloring with a fixed number of colors.Weizmann Institute of Science, Rehovot, Israel, November 2001."}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45753-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:33:07Z","timestamp":1556757187000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45753-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441861","9783540457534"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-45753-4_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}