{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T19:25:38Z","timestamp":1743017138029,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540939795"},{"type":"electronic","value":"9783540939801"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-540-93980-1_22","type":"book-chapter","created":{"date-parts":[[2009,1,12]],"date-time":"2009-01-12T00:12:21Z","timestamp":1231719141000},"page":"279-292","source":"Crossref","is-referenced-by-count":3,"title":["On the Maximum Edge Coloring Problem"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Lucarelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis","family":"Milis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10878-005-5483-4","volume":"9","author":"F.N. Afrati","year":"2005","unstructured":"Afrati, F.N., Aslanidis, T., Bampis, E., Milis, I.: Scheduling in switching networks with set-up delays. Journal of Combinatorial Optimization\u00a09, 49\u201357 (2005)","journal-title":"Journal of Combinatorial Optimization"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R","volume":"1","author":"P. Brucker","year":"1998","unstructured":"Brucker, P., Gladky, A., Hoogeveen, H., Koyalyov, M., Potts, C., Tautenham, T., van de Velde, S.: Scheduling a batching machine. Journal of Scheduling\u00a01, 31\u201354 (1998)","journal-title":"Journal of Scheduling"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Chetwynd, A.G., Hilton, A.J.W.: Regular graphs of high degree are 1-factorizable. In: Proceedings of the London Mathematical Society, vol.\u00a050, pp. 193\u2013206 (1985)","DOI":"10.1112\/plms\/s3-50.2.193"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1023\/A:1011441109660","volume":"5","author":"P. Crescenzi","year":"2001","unstructured":"Crescenzi, P., Deng, X., Papadimitriou, C.H.: On approximating a scheduling problem. Journal of Combinatorial Optimization\u00a05, 287\u2013297 (2001)","journal-title":"Journal of Combinatorial Optimization"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1007\/978-3-540-30551-4_76","volume-title":"Algorithms and Computation","author":"D. Werra de","year":"2004","unstructured":"de Werra, D., Demange, M., Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring on planar, bipartite and split graphs: Complexity and improved approximation. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 896\u2013907. Springer, Heidelberg (2004)"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0166-218X(95)00055-V","volume":"68","author":"D. Werra de","year":"1996","unstructured":"de Werra, D., Hoffman, A.J., Mahadev, N.V.R., Peled, U.N.: Restrictions and preassignments in preemptive open shop scheduling. Discrete Applied Mathematics\u00a068, 169\u2013188 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-36379-3_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Demange","year":"2002","unstructured":"Demange, M., de Werra, D., Monnot, J., Paschos, V.T.: Weighted node coloring: When stable sets are expensive. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 114\u2013125. Springer, Heidelberg (2002)"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ipl.2005.09.013","volume":"97","author":"B. Escoffier","year":"2006","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring: further complexity and approximability results. Information Processing Letters\u00a097, 98\u2013103 (2006)","journal-title":"Information Processing Letters"},{"key":"22_CR9","unstructured":"Finke, G., Jost, V., Queyranne, M., Seb\u0151, A.: Batch processing with interval graph compatibilities between tasks. Technical report, Cahiers du laboratoire Leibniz (2004), \n                    \n                      http:\/\/www-leibniz.imag.fr\/NEWLEIBNIZ\/LesCahiers\/index.xhtml"},{"key":"22_CR10","volume-title":"Edge-Colourings of Graphs","author":"S. Fiorini","year":"1977","unstructured":"Fiorini, S., Wilson, R.J.: Edge-Colourings of Graphs. Pitman, London (1977)"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1109\/TCOM.1985.1096336","volume":"33","author":"I.S. Gopal","year":"1985","unstructured":"Gopal, I.S., Wong, C.: Minimizing the number of switchings in a SS\/TDMA system. IEEE Transactions On Communications\u00a033, 497\u2013501 (1985)","journal-title":"IEEE Transactions On Communications"},{"key":"22_CR12","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 Journal on Computing\u00a010, 718\u2013720 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"1212","DOI":"10.1109\/TCOMM.2007.898848","volume":"55","author":"A. Kesselman","year":"2007","unstructured":"Kesselman, A., Kogan, K.: Nonpreemptive scheduling of optical switches. IEEE Transactions on Communications\u00a055, 1212\u20131219 (2007)","journal-title":"IEEE Transactions on Communications"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D. K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D.: \u00dcber graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen\u00a077, 453\u2013465 (1916)","journal-title":"Mathematische Annalen"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(92)90202-L","volume":"36","author":"M. Kubale","year":"1992","unstructured":"Kubale, M.: Some results concerning the complexity of restricted colorings of graphs. Discrete Applied Mathematics\u00a036, 35\u201346 (1992)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR16","unstructured":"Lucarelli, G., Milis, I., Paschos, V.T.: On a generalized graph coloring\/batch scheduling problem. In: 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), pp. 353\u2013360 (2007)"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An \n                    \n                      \n                    \n                    ${O(\\sqrt{|V|}|E|)}$\n                   algorithm for finding maximum matching in general graphs. In: 21st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Pemmaraju, S.V., Raman, R.: Approximation algorithms for the max-coloring problem. In: 32nd International Colloquium on Automata, Languages and Programming (ICALP), pp. 1064\u20131075 (2005)","DOI":"10.1007\/11523468_86"},{"key":"22_CR19","unstructured":"Pemmaraju, S.V., Raman, R., Varadarajan, K.R.: Buffer minimization using max-coloring. In: 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 562\u2013571 (2004)"},{"key":"22_CR20","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0167-6377(85)90042-2","volume":"4","author":"F. Rendl","year":"1985","unstructured":"Rendl, F.: On the complexity of decomposing matrices arising in satellite communication. Operations Research Letters\u00a04, 5\u20138 (1985)","journal-title":"Operations Research Letters"},{"key":"22_CR21","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. Diskret. Analiz.\u00a03, 25\u201330 (1964)","journal-title":"Diskret. Analiz."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-93980-1_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T12:05:11Z","timestamp":1558267511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-93980-1_22"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540939795","9783540939801"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-93980-1_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}