{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:07Z","timestamp":1781077687705,"version":"3.54.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,4,2]],"date-time":"2010-04-02T00:00:00Z","timestamp":1270166400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s00224-010-9262-y","type":"journal-article","created":{"date-parts":[[2010,4,1]],"date-time":"2010-04-01T13:43:49Z","timestamp":1270129429000},"page":"402-410","source":"Crossref","is-referenced-by-count":28,"title":["Vertex Cover Problem Parameterized Above and Below Tight Bounds"],"prefix":"10.1007","volume":"48","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,4,2]]},"reference":[{"key":"9262_CR1","first-page":"62","volume-title":"Proc. 6th Workshop on Algorithm Engineering and Experiments (ALENEX04)","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: Proc. 6th Workshop on Algorithm Engineering and Experiments (ALENEX04), pp. 62\u201369. ACM\/SIAM, New York\/Philadelphia (2004)"},{"issue":"3","key":"9262_CR2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00453-006-1214-1","volume":"45","author":"F.N. Abu-Khzam","year":"2006","unstructured":"Abu-Khzam, F.N., Langston, M.A., Shanbhag, P., Symons, C.T.: Scalable parallel algorithms for FPT problems. Algorithmica 45(3), 269\u2013284 (2006)","journal-title":"Algorithmica"},{"key":"9262_CR3","doi-asserted-by":"crossref","unstructured":"Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Proc. 13th International Symposium on Algorithms and Computation (ISAAC02). Lect. Notes Comput. Sci., vol. 2518, pp. 453\u2013464 (2002)","DOI":"10.1007\/3-540-36136-7_40"},{"issue":"4","key":"9262_CR4","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1016\/S0022-0000(03)00075-8","volume":"67","author":"J. Cheetham","year":"2003","unstructured":"Cheetham, J., Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.J.: Solving large FPT problems on coarse grained parallel machines. J. Comput. Syst. Sci. 67(4), 691\u2013706 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9262_CR5","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Simplicity is beauty: improved upper bounds for Vertex Cover. Technical Report 05-008, DePaul University, Chicago (2005)"},{"issue":"3","key":"9262_CR6","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","volume":"351","author":"P. Damaschke","year":"2006","unstructured":"Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3), 337\u2013350 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9262_CR7","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Proc. IWPEC2008. Lect. Notes Comput. Sci., vol. 5018: pp. 78\u201390 (2008)","DOI":"10.1007\/978-3-540-79723-4_9"},{"key":"9262_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"5","key":"9262_CR9","doi-asserted-by":"crossref","first-page":"1277","DOI":"10.1016\/j.ejc.2008.10.003","volume":"30","author":"L. Esperet","year":"2009","unstructured":"Esperet, L.: Boxicity of graphs with bounded degree. Eur. J. Comb. 30(5), 1277\u20131280 (2009)","journal-title":"Eur. J. Comb."},{"key":"9262_CR10","doi-asserted-by":"crossref","unstructured":"Fellows, M.R.: Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Proc. 20th International Workshop on Combinatorial Algorithms (IWOCA09), Lect. Notes Comput. Sci., vol. 5874, pp.\u00a02\u201310 (2009)","DOI":"10.1007\/978-3-642-10217-2_2"},{"key":"9262_CR11","doi-asserted-by":"crossref","unstructured":"Fernau, H.: On parameterized enumeration. In: Proc. 8th Annual International Computing and Combinatorics Conference (COCOON02). Lect. Notes Comput. Sci., vol. 2383: pp. 564\u2013573 (2002)","DOI":"10.1007\/3-540-45655-4_60"},{"key":"9262_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"1","key":"9262_CR13","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/j.tcs.2006.01.032","volume":"356","author":"S. Grigorieff","year":"2006","unstructured":"Grigorieff, S.: Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time D \u230alog\u2009mD \u230b. Theor. Comput. Sci. 356(1), 170\u2013185 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"9262_CR14","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9262_CR15","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of Vertex Cover variants. Theory Comput. Syst. 41(3), 501\u2013520 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9262_CR16","doi-asserted-by":"crossref","unstructured":"Gutin, G., Karapetyan, D., Razgon, I.: FPT algorithms in analysis of heuristics for extracting networks in linear programs. In; Proc. 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009). Lect. Notes Comput. Sci., vol. 5917, pp.\u00a0222\u2013233 (2009)","DOI":"10.1007\/978-3-642-11269-0_18"},{"issue":"2","key":"9262_CR17","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137\u2013153 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9262_CR18","doi-asserted-by":"crossref","unstructured":"Mishra, S., Raman, V., Saurabh, S., Sikdar, S., Subramanian, C.R.: The complexity of finding subgraphs whose matching number equals the vertex cover number. In: Proc. ISAAC 2007. Lect. Notes Comput. Sci., vol. 4835, pp. 268\u2013279 (2007)","DOI":"10.1007\/978-3-540-77120-3_25"},{"key":"9262_CR19","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"key":"9262_CR20","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Inf. Process. Lett. 73, 125\u2013129 (2000)","journal-title":"Inf. Process. Lett."},{"key":"9262_CR21","doi-asserted-by":"crossref","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT Is Fixed-Parameter Tractable. In: Proc. ICALP2008. Lect. Notes Comput. Sci., vol. 5125, pp. 551\u2013562 (2008)","DOI":"10.1007\/978-3-540-70575-8_45"},{"key":"9262_CR22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K","volume":"27","author":"B. Reed","year":"1998","unstructured":"Reed, B.: \u03c7, \u0394 and \u03c9. J. Graph Theory 27, 177\u2013212 (1998)","journal-title":"J. Graph Theory"},{"key":"9262_CR23","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall, New York (2001)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9262-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9262-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9262-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T18:34:30Z","timestamp":1558982070000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9262-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,2]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9262"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9262-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,2]]}}}