{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T17:40:26Z","timestamp":1648662026622},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T00:00:00Z","timestamp":1502928000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s00453-017-0362-9","type":"journal-article","created":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T10:06:29Z","timestamp":1502964389000},"page":"2941-2956","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Clique Clustering Yields a PTAS for Max-Coloring Interval Graphs"],"prefix":"10.1007","volume":"80","author":[{"given":"Tim","family":"Nonner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"issue":"5","key":"362_CR1","doi-asserted-by":"crossref","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. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"362_CR2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.jda.2013.11.003","volume":"26","author":"E Bampis","year":"2014","unstructured":"Bampis, E., Kononov, A., Lucarelli, G., Milis, I.: Bounded max-colorings of graphs. J. Disc. Algorithms 26, 56\u201368 (2014)","journal-title":"J. Disc. Algorithms"},{"key":"362_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-ptas for unsplittable flow on line graphs. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906), pp. 721\u2013729, (2006)","DOI":"10.1145\/1132516.1132617"},{"issue":"1","key":"362_CR4","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/1644015.1644028","volume":"6","author":"L Becchetti","year":"2009","unstructured":"Becchetti, L., Marchetti-Spaccamela, A., Vitaletti, A., Korteweg, P., Skutella, M., Stougie, L.: Latency-constrained aggregation in sensor networks. ACM Trans. Algorithms 6(1), 88\u201399 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"362_CR5","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1137\/S0097539703423941","volume":"33","author":"AL Buchsbaum","year":"2004","unstructured":"Buchsbaum, A.L., Karloff, H.J., Kenyon, C., Reingold, N., Thorup, M.: OPT versus LOAD in dynamic storage allocation. SIAM J. Comput. 33(3), 632\u2013646 (2004)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"362_CR6","doi-asserted-by":"crossref","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. Disc. Appl. Math. 157(4), 819\u2013832 (2009)","journal-title":"Disc. Appl. Math."},{"key":"362_CR7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2012.07.037","volume":"462","author":"L Epstein","year":"2012","unstructured":"Epstein, L., Levin, A.: On the max coloring problem. Theor. Comput. Sci. 462, 23\u201338 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"362_CR8","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, V.T.: Weighted coloring: further complexity and approximability results. Inf. Process. Lett 97(3), 98\u2013103 (2006)","journal-title":"Inf. Process. Lett"},{"issue":"2","key":"362_CR9","doi-asserted-by":"crossref","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. 57(2), 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"362_CR10","doi-asserted-by":"crossref","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. Disc. Appl. Math. 156(5), 556\u2013568 (2008)","journal-title":"Disc. Appl. Math."},{"key":"362_CR11","doi-asserted-by":"crossref","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\u00e1szl\u00f3, Schrijver, Alexander: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin (1988)"},{"issue":"2","key":"362_CR12","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0020-0190(97)00002-1","volume":"61","author":"DJ Guan","year":"1997","unstructured":"Guan, D.J., Xuding, Z.: A coloring problem for weighted graphs. Inf. Process. Lett 61(2), 77\u201381 (1997)","journal-title":"Inf. Process. Lett"},{"key":"362_CR13","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Shachnai, H.: Batch coloring flat graphs and thin. In :Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT\u201908), pp. 198\u2013209. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-69903-3_19"},{"issue":"1","key":"362_CR14","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"362_CR15","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463\u2013468 (1975)","journal-title":"J. ACM"},{"issue":"1","key":"362_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10878-010-9290-1","volume":"24","author":"T Kavitha","year":"2012","unstructured":"Kavitha, T., Mestre, J.: Max-coloring paths: tight bounds and extensions. J. Comb. Optim. 24(1), 1\u201314 (2012)","journal-title":"J. Comb. Optim."},{"key":"362_CR17","doi-asserted-by":"crossref","unstructured":"Mestre, J., Raman, R.: Max-coloring. In :Handbook of Combinatorial Optimization, Springer, New York, pp. 1871\u20131911, (2013)","DOI":"10.1007\/978-1-4419-7997-1_32"},{"key":"362_CR18","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.tcs.2015.10.047","volume":"613","author":"T Nonner","year":"2016","unstructured":"Nonner, T.: Capacitated max-batching with interval graph compatibilities. Theor. Comput. Sci. 613, 79\u201393 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"362_CR19","doi-asserted-by":"crossref","unstructured":"Pemmaraju, S. V., Raman, R.: Approximation algorithms for the max-coloring problem. In :Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP\u201905), vol. 5, pp. 1064\u20131075, (2005)","DOI":"10.1007\/11523468_86"},{"key":"362_CR20","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\u201904), pp. 562\u2013571, (2004)"},{"issue":"3","key":"362_CR21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/1978782.1978790","volume":"7","author":"SV Pemmaraju","year":"2011","unstructured":"Pemmaraju, S.V., Raman, R., Varadarajan, K.R.: Max-coloring and online coloring with bandwidths on interval graphs. ACM Trans. Algorithms 7(3), 35 (2011)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0362-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0362-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0362-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,5,30]],"date-time":"2018-05-30T15:29:59Z","timestamp":1527694199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0362-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,17]]},"references-count":21,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["362"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0362-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,17]]}}}