{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:22Z","timestamp":1725558982738},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241324"},{"type":"electronic","value":"9783540305590"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30559-0_22","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:01:42Z","timestamp":1278097302000},"page":"257-269","source":"Crossref","is-referenced-by-count":48,"title":["Linear Kernels in Linear Time, or How to Save k Colors in O(n 2) Steps"],"prefix":"10.1007","author":[{"given":"Benny","family":"Chor","sequence":"first","affiliation":[]},{"given":"Mike","family":"Fellows","sequence":"additional","affiliation":[]},{"given":"David","family":"Juedes","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","volume-title":"Computers and Intractability: a guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York (1979)"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: A still better performance guarantee for approximate graph coloring. Information Processing Letters\u00a045, 19\u201323 (1993)","journal-title":"Information Processing Letters"},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the ACM\u00a041, 960\u2013981 (1994)","journal-title":"Journal of the ACM"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and non-approximability \u2013 towards tight results. SIAM Journal on Computing\u00a027, 804\u2013915 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR5","first-page":"278","volume-title":"Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity","author":"U. Feige","year":"1996","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. In: Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, pp. 278\u2013289. IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(94)90039-6","volume":"50","author":"M. Demange","year":"1994","unstructured":"Demange, M., Grisoni, P., Paschos, V.T.: Approximation results for the minimum graph coloring problem. Information Processing Letters\u00a050, 19\u201323 (1994)","journal-title":"Information Processing Letters"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0020-0190(94)00113-8","volume":"52","author":"R. Hassin","year":"1994","unstructured":"Hassin, R., Lahav, S.: Maximizing the number of unused colors in the vertex coloring problem. Information Processing Letters\u00a052, 87\u201390 (1994)","journal-title":"Information Processing Letters"},{"key":"22_CR8","first-page":"160","volume-title":"Proceedings of the Sixth ACM-SIAM Symposium on Discrete Algorithms","author":"M.M. Halld\u00f3rsson","year":"1995","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvement. In: Proceedings of the Sixth ACM-SIAM Symposium on Discrete Algorithms, pp. 160\u2013169. ACM Press, New York (1995)"},{"key":"22_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/3-540-61310-2_10","volume-title":"Integer Programming and Combinatorial Optimization","author":"M.M. Halld\u00f3rsson","year":"1996","unstructured":"Halld\u00f3rsson, M.M.: Approximating k-set cover and complementary graph coloring. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 118\u2013131. Springer, Heidelberg (1996)"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1145\/258533.258599","volume-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing","author":"R.C. Duh","year":"1997","unstructured":"Duh, R.C., F\u00fcrer, M.: Approximation of k-set cover by semi-local optimization. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 256\u2013264. ACM Press, New York (1997)"},{"key":"22_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/3-540-44634-6_42","volume-title":"Algorithms and Data Structures","author":"D. Eppstein","year":"2001","unstructured":"Eppstein, D.: Small maximal independent sets and faster exact graph coloring. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol.\u00a02125, p. 462\u2013470. Springer, Heidelberg (2001)"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of the V-C dimension. Journal of Computer and System Sciences\u00a053 (1996)","DOI":"10.1006\/jcss.1996.0058"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I., Jia, W.: Vertex cover:further observations and further improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: Structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/6462.6502","volume":"18","author":"Z. Galil","year":"1986","unstructured":"Galil, Z.: Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys\u00a018, 23\u201338 (1986)","journal-title":"ACM Computing Surveys"},{"key":"22_CR17","series-title":"Annals of Discrete Mathematics","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics, vol.\u00a029. North Holland, Amsterdam (1986)"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1073\/pnas.43.9.842","volume":"43","author":"C. Berge","year":"1957","unstructured":"Berge, C.: Two theorems in graph theory. Proceedings of the National Academy of Sciences U.S.A.\u00a043, 842\u2013844 (1957)","journal-title":"Proceedings of the National Academy of Sciences U.S.A."},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n\n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing\u00a02, 225\u2013231 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR20","first-page":"17","volume-title":"21st Annual Symposium on Foundations of Computer Science","author":"S. Micali","year":"1980","unstructured":"Micali, S., Vazirani, V.V.: An \n \n \n \n ${\\it O}({\\sqrt{|v|}\\cdot|E|})$\n algorithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, pp. 17\u201327. IEEE, Los Alamitos (1980)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30559-0_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:30:00Z","timestamp":1620012600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30559-0_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241324","9783540305590"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30559-0_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}