{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:55Z","timestamp":1759638235793},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,17]],"date-time":"2014-10-17T00:00:00Z","timestamp":1413504000000},"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":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9948-7","type":"journal-article","created":{"date-parts":[[2014,10,16]],"date-time":"2014-10-16T15:00:42Z","timestamp":1413471642000},"page":"367-384","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Parameterizations of Test Cover with Bounded Test Sizes"],"prefix":"10.1007","volume":"74","author":[{"given":"R.","family":"Crowston","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Gutin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Muciaccia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Yeo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,17]]},"reference":[{"key":"9948_CR1","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N Alon","year":"2011","unstructured":"Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX- $$r$$ r -SAT above a tight lower bound. Algorithmica 61, 638\u2013655 (2011)","journal-title":"Algorithmica"},{"key":"9948_CR2","first-page":"67","volume":"24","author":"M Basavaraju","year":"2013","unstructured":"Basavaraju, M., Francis, M.C., Ramanujan, M.S., Saurabh, S.: Partially polynomial kernels for set cover and test cover. FSTTCS. LIPIcs 24, 67\u201378 (2013)","journal-title":"FSTTCS. LIPIcs"},{"issue":"8","key":"9948_CR3","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9948_CR4","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0095-8956(72)90025-1","volume":"12","author":"JA Bondy","year":"1972","unstructured":"Bondy, J.A.: Induced subsets. J. Comb. Theory, Ser. B 12, 201\u2013202 (1972)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9948_CR5","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1016\/j.jcss.2013.10.002","volume":"80","author":"R Crowston","year":"2014","unstructured":"Crowston, R., Fellows, M., Gutin, G., Jones, M., Kim, E.J., Rosamond, F., Ruzsa, I.Z., Thomass\u00e9, S., Yeo, A.: Satisfying more than half of a system of linear equations over GF(2): a multivariate approach. J. Comput. Syst. Sci. 80, 687\u2013696 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"9948_CR6","doi-asserted-by":"crossref","unstructured":"Crowston, R., Gutin, G., Jones, M., Saurabh, S., and Yeo, A.: Parameterized study of the test cover problem. In: MFCS 2012, Lect. Notes Comput. Sci. Vol. 7464, 283\u2013295 (2012)","DOI":"10.1007\/978-3-642-32589-2_27"},{"key":"9948_CR7","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/s00453-011-9550-1","volume":"64","author":"R Crowston","year":"2012","unstructured":"Crowston, R., Gutin, G., Jones, M., Yeo, A.: A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications. Algorithmica 64, 56\u201368 (2012)","journal-title":"Algorithmica"},{"key":"9948_CR8","doi-asserted-by":"crossref","unstructured":"Crowston, R., Jones, M., Mnich, M.: Max-cut parameterized above the Edwards\u2013Erd\u0151s bound. In: ICALP 2012, Lect. Notes Comput. Sci., vol. 7391, pp. 242\u2013253 (2012)","DOI":"10.1007\/978-3-642-31594-7_21"},{"key":"9948_CR9","doi-asserted-by":"crossref","unstructured":"De Bontridder, K.M.J., Lageweg, B.J., Lenstra, J.K., Orlin, J.B., and Stougie, L.: Branch and bound algorithms for the test-cover problem. In: ESA 2002, Lect. Notes Comput. Sci. Vol. 2461, pp. 223\u2013233 (2002)","DOI":"10.1007\/3-540-45749-6_23"},{"issue":"1\u20133","key":"9948_CR10","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/s10107-003-0414-6","volume":"98","author":"KMJ Bontridder De","year":"2003","unstructured":"De Bontridder, K.M.J., Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Hurkens, C.A.J., Lenstra, J.K., Ravi, R., Stougie, L.: Approximation algorithms for the test cover problem. Math. Program. B 98(1\u20133), 477\u2013491 (2003)","journal-title":"Math. Program. B"},{"key":"9948_CR11","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., and Saurabh, S.: Incompressibility through colors and IDs. In: 36th ICALP, Part I, Lect. Notes Comput. Sci. Vol. 5555, pp. 378\u2013389 (2009)","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"9948_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"key":"9948_CR13","doi-asserted-by":"crossref","first-page":"2.2","DOI":"10.1145\/1187436.1216579","volume":"11","author":"T Fahle","year":"2007","unstructured":"Fahle, T., Tiemann, K.: A faster branch-and-bound algorithm for the test-cover problem based on set-covering techniques. J. Exp. Algorithmics 11, 2.2 (2007)","journal-title":"J. Exp. Algorithmics"},{"key":"9948_CR14","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9948_CR15","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, A Guide to the Theory of NP-completeness (1979)"},{"key":"9948_CR16","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1016\/j.jcss.2010.05.001","volume":"76","author":"G Gutin","year":"2010","unstructured":"Gutin, G., Kim, E.J., Mnich, M., Yeo, A.: Betweenness parameterized above tight lower bound. J. Comput. Syst. Sci. 76, 872\u2013878 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"9948_CR17","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.ipl.2012.12.008","volume":"113","author":"G Gutin","year":"2013","unstructured":"Gutin, G., Muciaccia, G., Yeo, A.: (Non-)existence of polynomial kernels for the test cover problem. Inf. Proc. Lett. 113, 123\u2013126 (2013)","journal-title":"Inf. Proc. Lett."},{"key":"9948_CR18","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Ravi, R.: On the approximability of the minimum test collection problem. In: ESA 2001, Lect. Notes Comput. Sci. Vol. 2161, pp. 158\u2013169 (2001)","DOI":"10.1007\/3-540-44676-1_13"},{"key":"9948_CR19","first-page":"109","volume":"2001","author":"BV Halld\u00f3rsson","year":"2001","unstructured":"Halld\u00f3rsson, B.V., Minden, J.S., Ravi, R.: PIER: protein identification by epitope recognition. Curr. Comput. Mol. Biol. 2001, 109\u2013110 (2001)","journal-title":"Curr. Comput. Mol. Biol."},{"key":"9948_CR20","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, NY (1972)"},{"issue":"2","key":"9948_CR21","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"9948_CR22","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":"9948_CR23","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1137\/0906067","volume":"6","author":"BME Moret","year":"1985","unstructured":"Moret, B.M.E., Shapiro, H.D.: On minimizing a set of tests. SIAM J. Sci. Stat. Comput. 6, 983\u20131003 (1985)","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"9948_CR24","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, Oxford (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9948-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9948-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9948-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:14Z","timestamp":1559123114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9948-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,17]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9948"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9948-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,17]]}}}