{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:00:43Z","timestamp":1762297243040},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_59","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"646-658","source":"Crossref","is-referenced-by-count":4,"title":["Approximation Algorithms for Maximum Edge Coloring Problem"],"prefix":"10.1007","author":[{"given":"Wangsen","family":"Feng","sequence":"first","affiliation":[]},{"given":"Li\u2019ang","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Wanling","family":"Qu","sequence":"additional","affiliation":[]},{"given":"Hanpin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"59_CR1","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R.L. Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Proc. Cambridge Phil. Soc.\u00a037, 194\u2013197 (1941)","journal-title":"Proc. Cambridge Phil. Soc."},{"key":"59_CR2","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of computer computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"59_CR3","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S.: The complexity of near optimal graph coloring. J. ACM\u00a023, 43\u201349 (1976)","journal-title":"J. ACM"},{"key":"59_CR4","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0196-6774(88)90005-3","volume":"9","author":"J.S. Turner","year":"1988","unstructured":"Turner, J.S.: Almost all k-colorable graphs are easy to color. J. Algor.\u00a09, 63\u201382 (1988)","journal-title":"J. Algor."},{"key":"59_CR5","first-page":"25","volume":"3","author":"V.G. Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz.\u00a03, 25\u201330 (1964)","journal-title":"Diskret. Analiz."},{"key":"59_CR6","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I.J. Holyer","year":"1981","unstructured":"Holyer, I.J.: The NP-completeness of edge-coloring. SIAM J. Comp.\u00a010, 718\u2013720 (1981)","journal-title":"SIAM J. Comp."},{"key":"59_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-45753-4_11","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"U. Feige","year":"2002","unstructured":"Feige, U., Ofek, E., Wieder, U.: Approximating maximum edge coloring in multigraphs. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 108\u2013121. Springer, Heidelberg (2002)"},{"key":"59_CR8","unstructured":"Raniwala, A., Chiueh, T.-c.: Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In: INFOCOM, 2005, pp. 2223\u20132234 (2005)"},{"issue":"2","key":"59_CR9","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/997122.997130","volume":"8","author":"A. Raniwala","year":"2004","unstructured":"Raniwala, A., Gopalan, K., Chiueh, T.-c.: Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. Mobile Computing and Communications Review\u00a08(2), 50\u201365 (2004)","journal-title":"Mobile Computing and Communications Review"},{"key":"59_CR10","volume-title":"Approximation algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer, Berlin (2001)"},{"key":"59_CR11","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $O(|V|^{\\frac{1}{2}}|E|)$ algorithm for finding maximum matching in general graphs. In: Proc. 21 st IEEE FOCS, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"59_CR12","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proc. 15 th ACM STOC, pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_59.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:28Z","timestamp":1619516308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_59","relation":{},"subject":[]}}