{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:31:02Z","timestamp":1764783062322},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T00:00:00Z","timestamp":1211932800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,5]]},"DOI":"10.1007\/s00453-008-9199-6","type":"journal-article","created":{"date-parts":[[2008,5,27]],"date-time":"2008-05-27T11:32:36Z","timestamp":1211887956000},"page":"97-118","source":"Crossref","is-referenced-by-count":23,"title":["A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set"],"prefix":"10.1007","volume":"57","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,5,28]]},"reference":[{"key":"9199_CR1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/11847250_24","volume-title":"International Workshop on Parameterized and Exact Computation IWPEC","author":"F. Abu-Khzam","year":"2006","unstructured":"Abu-Khzam,\u00a0F., Fernau,\u00a0H.: Kernels: annotated, proper and induced. In: International Workshop on Parameterized and Exact Computation IWPEC. LNCS, vol. 4169, pp. 264\u2013275. Springer, Berlin (2006)"},{"key":"9199_CR2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/978-3-540-73951-7_38","volume-title":"Workshop on Algorithms and Data Structures WADS","author":"F.N. Abu-Khzam","year":"2007","unstructured":"Abu-Khzam,\u00a0F.N.: Kernelization algorithms for d-hitting set problems. In: Workshop on Algorithms and Data Structures WADS. LNCS, vol. 4619, pp. 434\u2013445. Springer, Berlin (2007)"},{"issue":"1","key":"9199_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","volume":"229","author":"J. Alber","year":"2001","unstructured":"Alber,\u00a0J., Gramm,\u00a0J., Niedermeier,\u00a0R.: Faster exact algorithms for hard problems: a parameterized point of view. Discrete Math. 229(1), 3\u201327 (2001)","journal-title":"Discrete Math."},{"key":"9199_CR4","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.jcss.2004.03.007","volume":"71","author":"J. Alber","year":"2005","unstructured":"Alber,\u00a0J., Fan,\u00a0H., Fellows,\u00a0M.R., Fernau,\u00a0H., Niedermeier,\u00a0R., Rosamond,\u00a0F., Stege,\u00a0U.: A refined search tree techniques for dominating set on planar graphs. J.\u00a0Comput. Syst. Sci. 71, 385\u2013405 (2005)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9199_CR5","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1016\/S0022-0000(03)00076-X","volume":"67","author":"R.S. Anand","year":"2003","unstructured":"Anand,\u00a0R.S., Erlebach,\u00a0T., Hall,\u00a0A., Stefanakos,\u00a0S.: Call control with k rejections. J.\u00a0Comput. Syst. Sci. 67, 707\u2013722 (2003)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9199_CR6","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-540-27801-6_15","volume-title":"Combinatorial Pattern Matching Symposium (CPM)","author":"V. Berry","year":"2004","unstructured":"Berry,\u00a0V., Nicolas,\u00a0F.: Maximum agreement and compatible supertrees. In: Combinatorial Pattern Matching Symposium (CPM). LNCS, vol. 3109, pp. 205\u2013219. Springer, Berlin (2004)"},{"key":"9199_CR7","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen,\u00a0J., Kanj,\u00a0I.A., Jia,\u00a0W.: Vertex cover: further observations and further improvements. J.\u00a0Algorithms 41, 280\u2013301 (2001)","journal-title":"J.\u00a0Algorithms"},{"key":"9199_CR8","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00453-004-1145-7","volume":"43","author":"J. Chen","year":"2005","unstructured":"Chen,\u00a0J., Kanj,\u00a0I.A., Xia,\u00a0G.: Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems. Algorithmica 43, 245\u2013273 (2005)","journal-title":"Algorithmica"},{"key":"9199_CR9","series-title":"LNCS","first-page":"238","volume-title":"Mathematical Foundations of Computer Science MFCS","author":"J. Chen","year":"2006","unstructured":"Chen,\u00a0J., Kanj,\u00a0I.A., Xia,\u00a0G.: Improved parameterized upper bounds for vertex cover. In: Mathematical Foundations of Computer Science MFCS. LNCS, vol. 4162, pp. 238\u2013249. Springer, Berlin (2006)"},{"key":"9199_CR10","series-title":"LNCS","first-page":"332","volume-title":"24th Symposium on Theoretical Aspects of Computer Science STACS","author":"P. Damaschke","year":"2007","unstructured":"Damaschke,\u00a0P.: The union of minimal hitting sets: parameterized combinatorial bounds and counting. In: 24th Symposium on Theoretical Aspects of Computer Science STACS. LNCS, vol. 4393, pp. 332\u2013343. Springer, Berlin (2007)"},{"key":"9199_CR11","doi-asserted-by":"crossref","unstructured":"Dinur,\u00a0I., Guruswami,\u00a0V., Khot,\u00a0S., Regev,\u00a0O.: A\u00a0new multilayered PCP and the hardness of hypergraph vertex cover. In: Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 595\u2013601 (2003)","DOI":"10.1145\/780542.780629"},{"key":"9199_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/11758471_31","volume-title":"Conference on Algorithms and Complexity CIAC","author":"M. Dom","year":"2006","unstructured":"Dom,\u00a0M., Guo,\u00a0J., H\u00fcffner,\u00a0F., Niedermeier,\u00a0R., Tru\u00df,\u00a0A.: Fixed-parameter tractability results for feedback set problems in tournaments. In: Conference on Algorithms and Complexity CIAC. LNCS, vol. 3998, pp. 320\u2013331. Springer, Berlin (2006)"},{"key":"9199_CR13","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1090\/dimacs\/049\/04","volume-title":"Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future","author":"R.G. Downey","year":"1999","unstructured":"Downey,\u00a0R.G., Fellows,\u00a0M.R., Stege,\u00a0U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, pp. 49\u201399. AMS, Providence (1999)"},{"key":"9199_CR14","series-title":"LNCS","first-page":"1","volume-title":"9th International Symposium on Graph Drawing GD","author":"V. Dujmovi\u0107","year":"2002","unstructured":"Dujmovi\u0107,\u00a0V., Fellows,\u00a0M.R., Hallett,\u00a0M., Kitching,\u00a0M., Liotta,\u00a0G., McCartin,\u00a0C., Nishimura,\u00a0N., Ragde,\u00a0P., Rosamond,\u00a0F.A., Suderman,\u00a0M., Whitesides,\u00a0S., Wood,\u00a0D.R.: A fixed-parameter approach to two-layer planarization. In: 9th International Symposium on Graph Drawing GD. LNCS, vol. 2265, pp. 1\u201315. Springer, Berlin (2002)"},{"key":"9199_CR15","unstructured":"Fernau,\u00a0H.: A\u00a0top-down approach to search-trees: Improved algorithmics for 3-Hitting Set. Technical Report TR04-073, Electronic Colloquium on Computational Complexity ECCC (2004)"},{"key":"9199_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.7155\/jgaa.00106","volume":"9","author":"H. Fernau","year":"2005","unstructured":"Fernau,\u00a0H.: Two-layer planarization: improving on parameterized algorithmics. J.\u00a0Graph Algorithms Appl. 9, 205\u2013238 (2005)","journal-title":"J.\u00a0Graph Algorithms Appl."},{"key":"9199_CR17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1007\/11758471_32","volume-title":"Conference on Algorithms and Complexity CIAC","author":"H. Fernau","year":"2006","unstructured":"Fernau,\u00a0H.: Parameterized algorithms for hitting set: the weighted case. In: Conference on Algorithms and Complexity CIAC. LNCS, vol. 3998, pp. 332\u2013343. Springer, Berlin (2006)"},{"key":"9199_CR18","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/11523468_16","volume-title":"Automata, Languages and Programming, 32nd International Colloquium, ICALP","author":"F.V. Fomin","year":"2005","unstructured":"Fomin,\u00a0F.V., Grandoni,\u00a0F., Kratsch,\u00a0D.: Measure and conquer: domination\u2014a case study. In: Automata, Languages and Programming, 32nd International Colloquium, ICALP. LNCS, vol. 3580, pp.\u00a0191\u2013203. Springer, Berlin (2005)"},{"key":"9199_CR19","volume-title":"Integer Programming","author":"R.S. Garfinkel","year":"1972","unstructured":"Garfinkel,\u00a0R.S., Nemhauser,\u00a0G.L.: Integer Programming. Wiley, New York (1972)"},{"key":"9199_CR20","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s00453-004-1090-5","volume":"39","author":"J. Gramm","year":"2004","unstructured":"Gramm,\u00a0J., Guo,\u00a0J., H\u00fcffner,\u00a0F., Niedermeier,\u00a0R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39, 321\u2013347 (2004)","journal-title":"Algorithmica"},{"key":"9199_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"Kullmann,\u00a0O.: New methods for 3-SAT decision and worst-case analysis. Theor. Comput. Sci. 223, 1\u201372 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"9199_CR22","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R. Niedermeier","year":"2003","unstructured":"Niedermeier,\u00a0R., Rossmanith,\u00a0P.: An efficient fixed-parameter algorithm for 3-Hitting Set. J.\u00a0Discrete Algorithms 1, 89\u2013102 (2003)","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9199_CR23","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","volume":"32","author":"R. Reiter","year":"1987","unstructured":"Reiter,\u00a0R.: A theory of diagnosis from first principles. Artif. Intell. 32, 57\u201395 (1987)","journal-title":"Artif. Intell."},{"key":"9199_CR24","volume-title":"Layered graph drawing","author":"M. Suderman","year":"2005","unstructured":"Suderman,\u00a0M.: Layered graph drawing. Ph.D. thesis, McGill University, Montr\u00e9al (2005)"},{"key":"9199_CR25","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.jalgor.2004.01.001","volume":"51","author":"M. Wahlstr\u00f6m","year":"2004","unstructured":"Wahlstr\u00f6m,\u00a0M.: Exact algorithms for finding minimum transversals in rank-3 hypergraphs. J.\u00a0Algorithms 51, 107\u2013121 (2004)","journal-title":"J.\u00a0Algorithms"},{"key":"9199_CR26","unstructured":"Wahlstr\u00f6m,\u00a0M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. thesis, Department of Computer and Information Science, Link\u00f6pings universitet, Sweden (2007). Available through http:\/\/www.diva-portal.org\/diva\/getDocument?urn_nbn_se_liu_diva-8714-1_fulltext.pdf"},{"key":"9199_CR27","unstructured":"Weihe,\u00a0K.: Covering trains by stations or the power of data reduction. In: Algorithms and Experiments ALEX 98, pp. 1\u20138 (1998). http:\/\/rtm.science.unitn.it\/alex98\/proceedings.html"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9199-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9199-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9199-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:02Z","timestamp":1559123102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9199-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,28]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["9199"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9199-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5,28]]}}}