{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:50:05Z","timestamp":1774417805395,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642220050","type":"print"},{"value":"9783642220067","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_16","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"183-194","source":"Crossref","is-referenced-by-count":6,"title":["Clique Clustering Yields a PTAS for max-Coloring Interval Graphs"],"prefix":"10.1007","author":[{"given":"Tim","family":"Nonner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"16_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-642-17517-6_32","volume-title":"Algorithms and Computation","author":"E. Bampis","year":"2010","unstructured":"Bampis, E., Kononov, A., Lucarelli, G., Milis, I.: Bounded max-colorings of graphs. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol.\u00a06506, pp. 353\u2013365. Springer, Heidelberg (2010)"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/11841036_11","volume-title":"Algorithms \u2013 ESA 2006","author":"L. Becchetti","year":"2006","unstructured":"Becchetti, L., Korteweg, P., Marchetti-Spaccamela, A., Skutella, M., Stougie, L., Vitaletti, A.: Latency constrained aggregation in sensor networks. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 88\u201399. Springer, Heidelberg (2006)"},{"issue":"4","key":"16_CR4","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1016\/j.dam.2008.06.013","volume":"157","author":"D. Werra de","year":"2009","unstructured":"de Werra, D., Demange, M., Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring on planar, bipartite and split graphs: Complexity and approximation. Discrete Applied Mathematics\u00a0157(4), 819\u2013832 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-540-77918-6_12","volume-title":"Approximation and Online Algorithms","author":"L. Epstein","year":"2008","unstructured":"Epstein, L., Levin, A.: On the max coloring problem. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol.\u00a04927, pp. 142\u2013155. Springer, Heidelberg (2008)"},{"issue":"3","key":"16_CR6","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. Inf. Process. Lett.\u00a097(3), 98\u2013103 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"16_CR7","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci.\u00a057(2), 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"16_CR8","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/j.dam.2006.03.039","volume":"156","author":"G. Finke","year":"2008","unstructured":"Finke, G., Jost, V., Queyranne, M., Seb\u00f6, A.: Batch processing with interval graph compatibilities between tasks. Discrete Applied Mathematics\u00a0156(5), 556\u2013568 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6schel","year":"1988","unstructured":"Gr\u00f6schel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1988)"},{"issue":"2","key":"16_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0020-0190(97)00002-1","volume":"61","author":"D.J. Guan","year":"1997","unstructured":"Guan, D.J., Zhu, X.: A coloring problem for weighted graphs. Inf. Process. Lett.\u00a061(2), 77\u201381 (1997)","journal-title":"Inf. Process. Lett."},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-540-69903-3_19","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"M.M. Halld\u00f3rsson","year":"2008","unstructured":"Halld\u00f3rsson, M.M., Shachnai, H.: Batch coloring flat graphs and thin. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a0SWAT, pp. 198\u2013209. Springer, Heidelberg (2008)"},{"issue":"1","key":"16_CR12","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM\u00a032(1), 130\u2013136 (1985)","journal-title":"Journal of the ACM"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM\u00a022, 463\u2013468 (1975)","journal-title":"J. ACM"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/978-3-642-10631-6_11","volume-title":"Algorithms and Computation","author":"T. Kavitha","year":"2009","unstructured":"Kavitha, T., Mestre, J.: Max-coloring paths: Tight bounds and extensions. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 87\u201396. Springer, Heidelberg (2009)"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-13731-0_18","volume-title":"Algorithm Theory - SWAT 2010","author":"T. Nonner","year":"2010","unstructured":"Nonner, T.: Capacitated max -batching with interval graph compatibilities. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 176\u2013187. Springer, Heidelberg (2010)"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1007\/11523468_86","volume-title":"Automata, Languages and Programming","author":"S.V. Pemmaraju","year":"2005","unstructured":"Pemmaraju, S.V., Raman, R.: Approximation algorithms for the max-coloring problem. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1064\u20131075. Springer, Heidelberg (2005)"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Pemmaraju, S.V., Raman, R., Varadarajan, K.: Max-coloring and online coloring with bandwidths on interval graphs. ACM Transactions on Algorithms (accepted for publication)","DOI":"10.1145\/1978782.1978790"},{"key":"16_CR18","unstructured":"Pemmaraju, S.V., Raman, R., Varadarajan, K.: Buffer minimization using max-coloring. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 562\u2013571 (2004)"},{"key":"16_CR19","unstructured":"Raman, R.: Personal communication (2010)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T07:03:56Z","timestamp":1553843036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}