{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T19:07:57Z","timestamp":1710356877206},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,3,14]],"date-time":"2009-03-14T00:00:00Z","timestamp":1236988800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s10878-009-9223-z","type":"journal-article","created":{"date-parts":[[2009,3,13]],"date-time":"2009-03-13T16:01:00Z","timestamp":1236960060000},"page":"429-442","source":"Crossref","is-referenced-by-count":7,"title":["On the max-weight edge coloring problem"],"prefix":"10.1007","volume":"20","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 T.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,3,14]]},"reference":[{"key":"9223_CR1","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10878-005-5483-4","volume":"9","author":"FN Afrati","year":"2005","unstructured":"Afrati FN, Aslanidis T, Bampis E, Milis I (2005) Scheduling in switching networks with set-up delays. J\u00a0Comb Optim 9:49\u201357","journal-title":"J\u00a0Comb Optim"},{"key":"9223_CR2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0166-218X(00)00358-9","volume":"114","author":"VA Bojarshinov","year":"2001","unstructured":"Bojarshinov VA (2001) Edge and total coloring of interval graphs. Discrete Appl Math 114:23\u201328","journal-title":"Discrete Appl Math"},{"key":"9223_CR3","doi-asserted-by":"crossref","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, Kovalyov M, Potts C, Tautenham T, van de Velde S (1998) Scheduling a batching machine. J Sched 1:31\u201354","journal-title":"J Sched"},{"key":"9223_CR4","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1023\/A:1011441109660","volume":"5","author":"P Crescenzi","year":"2001","unstructured":"Crescenzi P, Deng X, Papadimitriou ChH (2001) On approximating a scheduling problem. J Comb Optim 5:287\u2013297","journal-title":"J Comb Optim"},{"key":"9223_CR5","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"896","DOI":"10.1007\/978-3-540-30551-4_76","volume-title":"15th International symposium on algorithms and computation (ISAAC\u201904)","author":"D Werra de","year":"2004","unstructured":"de Werra D, Demange M, Escoffier B, Monnot J, Paschos VTh (2004) Weighted coloring on planar, bipartite and split graphs: Complexity and improved approximation. In: 15th International symposium on algorithms and computation (ISAAC\u201904). LNCS, vol 3341. Springer, Berlin, pp 896\u2013907"},{"key":"9223_CR6","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/3-540-36379-3_11","volume-title":"28th Workshop on graph-theoretic concepts in computer science (WG\u201902)","author":"M Demange","year":"2002","unstructured":"Demange M, de Werra D, Monnot J, Paschos VTh (2002) Weighted node coloring: When stable sets are expensive. In: 28th Workshop on graph-theoretic concepts in computer science (WG\u201902). LNCS, vol 2573. Springer, Berlin, pp 114\u2013125"},{"key":"9223_CR7","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.ipl.2005.09.013","volume":"97","author":"B Escoffier","year":"2006","unstructured":"Escoffier B, Monnot J, Paschos VTh (2006) Weighted coloring: further complexity and approximability results. Inf Process Lett 97:98\u2013103","journal-title":"Inf Process Lett"},{"key":"9223_CR8","unstructured":"Finke G, Jost V, Queyranne M, Seb\u0151 A (2004) Batch processing with interval graph compatibilities between tasks. Technical report, Cahiers du laboratoire Leibniz; available at http:\/\/www-leibniz.imag.fr\/NEWLEIBNIZ\/LesCahiers\/index.xhtml"},{"key":"9223_CR9","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1109\/TCOM.1985.1096336","volume":"33","author":"IS Gopal","year":"1985","unstructured":"Gopal IS, Wong C (1985) Minimizing the number of switchings in a SS\/TDMA system. IEEE Trans Commun 33:497\u2013501","journal-title":"IEEE Trans Commun"},{"key":"9223_CR10","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer I (1981) The NP-completeness of edge-coloring. SIAM J Comput 10:718\u2013720","journal-title":"SIAM J Comput"},{"key":"9223_CR11","doi-asserted-by":"crossref","unstructured":"Kesselman A, Kogan K (2004) Non-preemptive scheduling of optical switches. In: 47th IEEE global telecommunications conference (GLOBECOM\u201904), vol\u00a03, pp 1840\u20131844","DOI":"10.1109\/GLOCOM.2004.1378305"},{"key":"9223_CR12","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D Konig","year":"1916","unstructured":"Konig D (1916) Uber graphen und ihre anwendung auf determinantentheorie und mengenlehre. Math Ann 77:453\u2013465","journal-title":"Math Ann"},{"key":"9223_CR13","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/322092.322101","volume":"25","author":"EL Lawler","year":"1978","unstructured":"Lawler EL, Labetoulle J (1978) On preemptive scheduling of unrelated parallel processors by linear programming. J Assoc Comput Mach 25:612\u2013619","journal-title":"J Assoc Comput Mach"},{"key":"9223_CR14","doi-asserted-by":"crossref","unstructured":"Micali S, Vazirani VV (1980) An ${O(\\sqrt{|V|}|E|)}$ algorithm for finding maximum matching in general graphs. In: 21st Annual IEEE symposium on foundations of computer science (FOCS\u201980), pp 17\u201327","DOI":"10.1109\/SFCS.1980.12"},{"key":"9223_CR15","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"1064","DOI":"10.1007\/11523468_86","volume-title":"32nd international colloquium on automata, languages and programming (ICALP\u201905)","author":"SV Pemmaraju","year":"2005","unstructured":"Pemmaraju SV, Raman R (2005) Approximation algorithms for the max-coloring problem. In: 32nd international colloquium on automata, languages and programming (ICALP\u201905). LNCS, vol 3580. Springer, Berlin, pp 1064\u20131075"},{"key":"9223_CR16","unstructured":"Pemmaraju SV, Raman R, Varadarajan KR (2004) Buffer minimization using max-coloring. In: 15th ACM-SIAM symposium on discrete algorithms (SODA\u201904), pp 562\u2013571"},{"key":"9223_CR17","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0167-6377(85)90042-2","volume":"4","author":"F Rendl","year":"1985","unstructured":"Rendl F (1985) On the complexity of decomposing matrices arising in satellite communication. Oper Res Lett 4:5\u20138","journal-title":"Oper Res Lett"},{"key":"9223_CR18","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing VG (1964) On an estimate of the chromatic class of a p-graph. Diskretn Anal 3:25\u201330","journal-title":"Diskretn Anal"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9223-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9223-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9223-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9223-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,14]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9223"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9223-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,14]]}}}