103
Views
9
CrossRef citations to date
0
Altmetric
Section A

Parameterized algorithmics for d-Hitting Set

Pages 3157-3174 | Received 03 Jul 2008, Accepted 09 Jul 2009, Published online: 04 Nov 2010

References

  • Chen , J. , Kanj , I. A. and Xia , G. 2006 . “ Improved parameterized upper bounds for vertex cover ” . In Mathematical Foundations of Computer Science MFCS , Edited by: Kralovic , R. and Urzyczyn , P. 238 – 249 . Berlin : Springer . Lecture Notes in Computer Science, Vol. 4162
  • Dinur , I. , Guruswami , V. , Khot , S. and Regev , O. A new multilayered PCP and the hardness of hypergraph vertex cover . Proceedings of the 35th ACM Symposium on Theory of Computing (STOC) . pp. 595 – 601 . ACM Press .
  • Downey , R. G. and Fellows , M. R. 1999 . “ Parameterized Complexity ” . Berlin : Springer .
  • Eppstein , D. 2006 . Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms . ACM Trans. Algorithms , 2 : 492 – 509 .
  • Fernau , H. 2010 . A top-down approach to search-trees: Improved algorithmics for 3-Hitting Set . Algorithmica , 57 : 97 – 118 .
  • Fernau , H. 2005 . Two-layer planarization: improving on parameterized algorithmics . J. Graph Algorithms Appl , 9 : 205 – 238 .
  • Fernau , H. 2010 . Parameterized algorithms for d-Hitting Set: The weighted case . Theor. Comput. Sci. , 411 ( 16–18 ) : 1698 – 1713 .
  • Fomin , F. V. , Grandoni , F. and Kratsch , D. 2005 . “ Measure and conquer: domination – a case study ” . In Automata, Languages and Programming, 32nd International Colloquium, ICALP , Edited by: Caires , L. , Italiano , G. F. , Monteiro , L. , Palamidessi , C. and Yung , M. 191 – 203 . Berlin : Springer . Lecture Notes in Computer Science, Vol. 3580
  • Niedermeier , R. and Rossmanith , P. 2003 . An efficient fixed-parameter algorithm for 3-Hitting Set . J. Discrete Algorithms , 1 : 89 – 102 .
  • Raman , V. , Saurabh , S. and Sikdar , S. 2005 . “ Improved exact exponential algorithms for vertex bipartization and other problems ” . In Italian Conference on Theoretical Computer Science ICTCS , Edited by: Coppo , M. , Lodi , E. and Michele Pinna , G. 375 – 389 . Berlin : Springer . Lecture Notes in Computer Science, vol. 3701
  • Reiter , R. 1987 . A theory of diagnosis from first principles . Artif. Intell , 32 : 57 – 95 .
  • Wahlström , M. 2004 . Exact algorithms for finding minimum transversals in rank-3 hypergraphs . J. Algorithms , 51 : 107 – 121 .
  • Wahlström , M. 2007 . Algorithms, measures and upper bounds for satisfiability and related problems , Sweden : Department of Computer and Information Science, Linköpings universitet . Ph.D. thesis
  • Wernicke , S. , Alber , J. , Gramm , J. , Guo , J. and Niedermeier , R. 2006 . The computational complexity of avoiding forbidden submatrices by row deletions . Int. J. Found. Comput. Sci. , 17 : 1467 – 1484 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.