{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:17:07Z","timestamp":1760440627613},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662006"},{"type":"electronic","value":"9783540486862"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48686-0_28","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:12Z","timestamp":1184586852000},"page":"281-290","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the Complexity of Approximating Colored-Graph Problems Extended Abstract"],"prefix":"10.1007","author":[{"given":"Andrea E. F.","family":"Clementi","sequence":"first","affiliation":[]},{"given":"Pierluigi","family":"Crescenzi","sequence":"additional","affiliation":[]},{"given":"Gianluca","family":"Rossi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,6,25]]},"reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01277956","volume":"5","author":"N. Alon","year":"1995","unstructured":"Alon, N., Feige, U., Wigderson, A., And Zuckerman, D. Derandomized graph products. Computational Complexity 5 (1995), 60\u201375.","journal-title":"Computational Complexity"},{"key":"28_CR2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K. A. Appel","year":"1977","unstructured":"Appel, K., And Haken, W. Every planar map is four colorable. part I: discharging. Illinois J. Math. 21 (1977), 429\u2013490.","journal-title":"Illinois J. Math."},{"key":"28_CR3","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1215\/ijm\/1256049012","volume":"21","author":"K. A. Appel","year":"1977","unstructured":"Appel, K., And Haken, W. Every planar map is four colorable. part II: reducibility. Illinois J. Math. 21 (1977), 491\u2013567.","journal-title":"Illinois J. Math."},{"key":"28_CR4","unstructured":"Berman, P., And Karpinski, M. On some tighter inapproximability results. Further improvements. Tech. Rep. TR98-065, ECCC, 1998."},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. A. Boppana","year":"1992","unstructured":"Boppana, R., And Halld\u00d3rsson, M. M. Approximating maximum independent sets by excluding subgraphs. Bit 32 (1992), 180\u2013196.","journal-title":"Bit"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1109\/90.491013","volume":"4","author":"A. A. Clementi","year":"1996","unstructured":"Clementi, A., And Di Ianni, M. On the hardness of approximating optimum schedule problems in store and forward networks. IEEE\/ACM Transaction on Networking 4 (1996), 272\u2013280.","journal-title":"IEEE\/ACM Transaction on Networking"},{"key":"28_CR7","unstructured":"Feige, U., And Kilian, J. Zero knowledge and the chromatic number. In Proc. Eleventh Ann. IEEE Conf. on Comp. Complexity (1996), IEEE Computer Society, pp. 278\u2013287."},{"key":"28_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. Garey","year":"1976","unstructured":"Garey, M., Johnson, D., And Stockmeyer, L. Some simplified NP-complete graph problems. Theoretical Comput. Sci. 1 (1976), 237\u2013267.","journal-title":"Theoretical Comput. Sci."},{"key":"28_CR9","volume-title":"Computers and Intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., AND Johnson, D. S.Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco, 1979."},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. X. Goemans","year":"1995","unstructured":"Goemans, M. X., AND Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (1995b), 1115\u20131145.","journal-title":"J. ACM"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M. M. Halld\u00d3rsson","year":"1993","unstructured":"Halld\u00d3rsson, M. M. A still better performance guarantee for approximate graph coloring. Inform. Process. Lett. 45 (1993a), 19\u201323.","journal-title":"Inform. Process. Lett."},{"key":"28_CR12","unstructured":"H\u00c5stad, J. Clique is hard to approximate within n1 \u2212 \u2208. In Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. (1996), IEEE Computer Society, pp. 627\u2013636."},{"key":"28_CR13","unstructured":"H\u00c5stad, J. Some optimal inapproximability results. In Proc. 29th Ann. ACM Symp. on Theory of Comp. (1997), ACM, pp. 1\u201310."},{"key":"28_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D. S. Hochbaum","year":"1983","unstructured":"Hochbaum, D. S. Efficient bounds for the stable set, vertex cover and set packing problems. Disc. Appl. Math. 6 (1983), 243\u2013254.","journal-title":"Disc. Appl. Math."},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"Karger, D., Motwani, R., AND Sudan, M. Approximate graph coloring by semidefinite programming. J. ACM 45 (1998), 246\u2013265.","journal-title":"J. ACM"},{"key":"28_CR16","unstructured":"Khanna, S., Linial, N., AND Safra, S. On the hardness of approximating the chromatic number. In Proc. 1st Israel Symp. on Theory of Computing and Systems (1992), IEEE Computer Society, pp. 250\u2013260."},{"key":"28_CR17","volume-title":"Introduction to parallel algorithms and architectures: arrays, trees, hypercubes","author":"F. Leighton","year":"1992","unstructured":"Leighton, F.Introduction to parallel algorithms and architectures: arrays, trees, hypercubes. Morgan Kaufmann, San Mateo, CA, 1992."},{"key":"28_CR18","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L. Lovasz","year":"1975","unstructured":"Lovasz, L. Three short proofs in graph theory. J. Combin. Theory 19 (1975), 269\u2013271.","journal-title":"J. Combin. Theory"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., AND Speckenmeyer, E. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inf. 22 (1985), 115\u2013123.","journal-title":"Acta Inf."},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C. H., AND Yannakakis, M. Optimization, approximation, and complexity classes. J. Comput. System Sci. 43 (1991), 425\u2013440.","journal-title":"J. Comput. System Sci."},{"key":"28_CR21","unstructured":"Trevisan, L. Approximating satisfiable satisfiability problems. In Proc. 5th Ann. European Symp. on Algorithms (1997), Springer-Verlag, pp. 472\u2013485."},{"key":"28_CR22","unstructured":"Zwick, U. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms (1998), ACM-SIAM, p. 201."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48686-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T19:46:58Z","timestamp":1558468018000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48686-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662006","9783540486862"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-48686-0_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"25 June 1999","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}