{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:47:10Z","timestamp":1725544030951},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540345978"},{"type":"electronic","value":"9783540345985"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11764298_21","type":"book-chapter","created":{"date-parts":[[2006,5,19]],"date-time":"2006-05-19T08:37:56Z","timestamp":1148027876000},"page":"231-240","source":"Crossref","is-referenced-by-count":0,"title":["Kernels for the Vertex Cover Problem on the Preferred Attachment Model"],"prefix":"10.1007","author":[{"given":"Josep","family":"D\u00edaz","sequence":"first","affiliation":[]},{"given":"Jordi","family":"Petit","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","first-page":"62","volume-title":"Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics","author":"F.N. Abu-Khzam","year":"2004","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: Theory and experiments. In: Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA, pp. 62\u201369. SIAM, Philadelphia (2004)"},{"key":"21_CR2","first-page":"69","volume-title":"Handbook of graphs and networks","author":"A.-L. Barab\u00e1si","year":"2003","unstructured":"Barab\u00e1si, A.-L.: Emergence of scaling in complex networks. In: Handbook of graphs and networks, pp. 69\u201384. Wiley-VCH, Weinheim (2003)"},{"issue":"5439","key":"21_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A.-L. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science\u00a0286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"issue":"3","key":"21_CR4","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/rsa.1009","volume":"18","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B., Riordan, O., Spencer, J., Tusn\u00e1dy, G.: The degree sequence of a scale-free random graph process. Random Structures Algorithms\u00a018(3), 279\u2013290 (2001)","journal-title":"Random Structures Algorithms"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J.F. Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within p. SIAM J. Computing\u00a022, 560\u2013572 (1993)","journal-title":"SIAM J. Computing"},{"key":"21_CR6","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Simplicity is beauty: Improved upper bounds for vertex cover. Technical Report 05-008, Texas A&M University, Utrecht, the Netherlands (April 2005)"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Clauset, A., Moore, C.: Accuracy and scaling phenomena in internet mapping. Phys. Rev. Lett.\u00a094 (2005)","DOI":"10.1103\/PhysRevLett.94.018701"},{"key":"21_CR8","volume-title":"Monographs in Computer Science","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science, Springer, New York (1999)"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_26","volume-title":"Algorithms and Computation","author":"M.R. Fellows","year":"2001","unstructured":"Fellows, M.R.: Parameterized complexity: the main ideas and some research frontiers. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, Springer, Heidelberg (2001)"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-39890-5_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R.: Blow-ups, win\/win\u2019s, and crown rules: Some new directions in fpt. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 1\u201312. Springer, Heidelberg (2003)"},{"key":"21_CR11","volume-title":"17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02006)","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Large measure and conquer: A simple O (20.288 n\n                           ) independent set algorithm. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02006), ACM and SIAM, New York (2006)"},{"issue":"4","key":"21_CR12","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results (electronic). J. ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1007\/11523468_84","volume-title":"Automata, Languages and Programming","author":"G. Karakostas","year":"2005","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1043\u20131050. Springer, Heidelberg (2005)"},{"key":"21_CR14","first-page":"85","volume-title":"Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972)","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pp. 85\u2013103. Plenum, New York (1972)"},{"issue":"1","key":"21_CR15","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inform.\u00a022(1), 115\u2013123 (1985)","journal-title":"Acta Inform."},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: structural properties and algorithms. Math. Programming\u00a08, 232\u2013248 (1975)","journal-title":"Math. Programming"},{"key":"21_CR17","first-page":"35","volume-title":"Handbook of graphs and networks","author":"M.E.J. Newman","year":"2003","unstructured":"Newman, M.E.J.: Random graphs as models of networks. In: Handbook of graphs and networks, pp. 35\u201368. Wiley-VCH, Weinheim (2003)"},{"key":"21_CR18","unstructured":"Robson, J.M.: Finding a maximum independent set in time O(2n\/4). manuscript (2001), \n                    \n                      http:\/\/dept-info.labri.fr\/~robson\/mis\/techrep.html"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11764298_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:10:53Z","timestamp":1619507453000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11764298_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540345978","9783540345985"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11764298_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}