{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:49Z","timestamp":1725490249177},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742074"},{"type":"electronic","value":"9783540742081"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_14","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T14:52:26Z","timestamp":1188226346000},"page":"189-203","source":"Crossref","is-referenced-by-count":2,"title":["Soft Edge Coloring"],"prefix":"10.1007","author":[{"given":"Chadi","family":"Kari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoo-Ah","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seungjoon","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minho","family":"Shin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","unstructured":"Raniwala, A., Chiueh, T.: Architecture and algorithms for an IEEE 802.11-based multi-ch annel wireless mesh network. In: Proceedings of Infocom (March 2005)"},{"key":"14_CR2","unstructured":"Kyasanur, P., Vaidya, N.H.: Routing and interface assignment in multi-channel multi-interfa ce wireless networks. In: Proceedings of WCNC (March 2005)"},{"key":"14_CR3","volume-title":"Proceedings of ACM MobiCom","author":"M. Alicherry","year":"2005","unstructured":"Alicherry, M., Bhatia, R., Li, L.E.: Joint channel assignment and routing for throughput optimization in mu lti-radio wireless mesh networks. In: Proceedings of ACM MobiCom, ACM Press, New York (2005)"},{"key":"14_CR4","volume-title":"MASS","author":"M. Shin","year":"2006","unstructured":"Shin, M., Lee, S., Kim, Y.A.: Distributed channel assignment for multi-radio wireless networks. In: MASS. The Third IEEE International Conference on Mobile Ad-hoc and Sensor Systems, IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"14_CR5","unstructured":"Kann, V., Khanna, S., Lagergren, J., Panconesi, A.: On the hardness of max k-cut and its dual. In: Proc. 5th Israel Symposium on Theory and Computing Systems (ISTCS), pp. 61\u201367 (1996)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-59408-6_37","volume-title":"Integer Programming and Combinatorial Optimization","author":"A. Frieze","year":"1995","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for MAX k-CUT and MAX BISECTION. In: Balas, E., Clausen, J. (eds.) Integer Programming and Combinatorial Optimization. LNCS, vol.\u00a0920, pp. 1\u201313. Springer, Heidelberg (1995)"},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","volume-title":"Stochastic Algorithms: Foundations and Applications","author":"S. Fitzpatrick","year":"2001","unstructured":"Fitzpatrick, S., Meertens, L.: An experimental assessment of a stochastic, anytime, decentralized, soft colourer for sparse graphs. In: Steinh\u00f6fel, K. (ed.) SAGA 2001. LNCS, vol.\u00a02264, Springer, Heidelberg (2001)"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/3-540-36494-3_46","volume-title":"STACS 2003","author":"P. Damaschke","year":"2003","unstructured":"Damaschke, P.: Distributed soft path coloring. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 523\u2013534. Springer, Heidelberg (2003)"},{"issue":"4","key":"14_CR9","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I.: The np-completeness of edge-coloring. SIAM J. Computing\u00a010(4), 718\u2013720 (1981)","journal-title":"SIAM J. Computing"},{"key":"14_CR10","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 (russian). Diskret. Analiz.\u00a03, 25\u201330 (1964)","journal-title":"Diskret. Analiz."},{"issue":"3","key":"14_CR11","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1137\/0403035","volume":"3","author":"T. Nishizeki","year":"1990","unstructured":"Nishizeki, T., Kashiwagi, K.: On the 1.1 edge-coloring of multigraphs. SIAM J. Disc. Math.\u00a03(3), 391\u2013410 (1990)","journal-title":"SIAM J. Disc. Math."},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0020-0190(98)00138-0","volume":"68","author":"A. Caprara","year":"1998","unstructured":"Caprara, A., Rizzi, R.: Improving a family of approximation algorithms to edge color multigraphs. Information Processing Letters\u00a068(1), 11\u201315 (1998)","journal-title":"Information Processing Letters"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Kari, C., Kim, Y.A., Lee, S., Russell, A., Shin, M.: Soft edge coloring (2007), Full version available at http:\/\/www.engr.uconn.edu\/~ykim\/soft.pdf","DOI":"10.1007\/978-3-540-74208-1_14"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/SFCS.1994.365710","volume-title":"Proc. 35th IEEE Symposium on Foundations of Computer Science","author":"D. Karger","year":"1994","unstructured":"Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. In: Proc. 35th IEEE Symposium on Foundations of Computer Science, pp. 2\u201313. IEEE Computer Society Press, Los Alamitos (1994)"},{"issue":"1","key":"14_CR15","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F. Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization\u00a05(1), 13\u201351 (1995)","journal-title":"SIAM Journal on Optimization"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Grotschel","year":"1981","unstructured":"Grotschel, M., Lovasz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"14_CR17","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Grotschel","year":"1987","unstructured":"Grotschel, M., Lovasz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer, Heidelberg (1987)"},{"key":"14_CR18","unstructured":"Nesterov, V., Nemirovskii, A.: Self-concordant functions and polynomial time methods in convex programming. Central Economical and Mathematical Institute, U.S.S.R. Academy of Science, Moscow (1990)"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Nesterov, V., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. SIAM (1994)","DOI":"10.1137\/1.9781611970791"},{"key":"14_CR20","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1983","unstructured":"Golub, G.H., Loan, C.F.V.: Matrix Computations. The Johns Hopkins University Press, Baltimore (1983)"},{"key":"14_CR21","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"14_CR22","volume-title":"The asymptotic theory of extreme order statistics","author":"J. Galambos","year":"1978","unstructured":"Galambos, J.: The asymptotic theory of extreme order statistics. Wiley, New York (1978)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T16:29:31Z","timestamp":1556814571000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}