×

zbMATH — the first resource for mathematics

Parameterized algorithms for \(d\)-hitting set: the weighted case. (English) Zbl 1192.68824
Summary: We are going to analyze search tree algorithms for Weighted \(d\)-Hitting Set. Although the algorithms that we develop are fairly simple, their analysis is technically involved. We compare the weighted case with the previously analyzed unweighted one, exhibiting that the advantage of the unweighted case dwindles with growing \(d\).

MSC:
68W05 Nonnumerical algorithms
68P10 Searching and sorting
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chen, J.; Kanj, I.A.; Jia, W., Vertex cover: further observations and further improvements, Journal of algorithms, 41, 280-301, (2001) · Zbl 1017.68087
[2] Dom, M.; Guo, J.; Hüffner, F.; Niedermeier, R.; Truß, A., Fixed-parameter tractability results for feedback set problems in tournaments, (), 320-331 · Zbl 1183.68419
[3] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer · Zbl 0914.68076
[4] Dujmović, V.; Fellows, M.R.; Hallett, M.; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.A.; Suderman, M.; Whitesides, S.; Wood, D.R., A fixed-parameter approach to 2-layer planarization, Algorithmica, 45, 159-182, (2006) · Zbl 1095.68081
[5] Eppstein, D., Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms, ACM transactions on algorithms, 2, 4, 492-509, (2006) · Zbl 1321.68558
[6] H. Fernau, A top-down approach to search-trees: Improved algorithmics for 3-Hitting Set, Technical Report TR04-073, Electronic Colloquium on Computational Complexity ECCC, 2004. An updated version of the part featuring 3- HS has been accepted to Algorithmica
[7] Fernau, H., Two-layer planarization: improving on parameterized algorithmics, Journal of graph algorithms and applications, 9, 205-238, (2005) · Zbl 1108.68062
[8] Fernau, H., Parameterized algorithms for \schitting set: the weighted case, (), 332-343 · Zbl 1183.68426
[9] Fernau, H., Parameterized algorithmics for linear arrangement problems, Discrete applied mathematics, 156, 3166-3177, (2008) · Zbl 1178.68376
[10] Fernau, H.; Kaufmann, M.; Poths, M., Comparing trees via crossing minimization, (), 457-469 · Zbl 1172.05315
[11] Fernau, H.; Raible, D., Searching trees: an essay, (), 59-70 · Zbl 1241.68058
[12] Fomin, F.V.; Grandoni, F.; Kratsch, D., Measure and conquer: domination — A case study, (), 191-203 · Zbl 1082.68866
[13] de Kleer, J.; Mackworth, A.K.; Reiter, R., Characterizing diagnoses and systems, Artificial intelligence, 56, 197-222, (1992) · Zbl 0772.68085
[14] Niedermeier, R.; Rossmanith, P., An efficient fixed-parameter algorithm for 3-hitting set, Journal of discrete algorithms, 1, 89-102, (2003) · Zbl 1118.68511
[15] Niedermeier, R.; Rossmanith, P., On efficient fixed parameter algorithms for weighted vertex cover, Journal of algorithms, 47, 63-77, (2003) · Zbl 1046.68058
[16] ()
[17] Plesník, J., Equivalence between the minimum covering problem and the maximum matching problem, Discrete mathematics, 49, 315-317, (1984) · Zbl 0581.05045
[18] Plesník, J., Constrained weighted matchings and edge coverings in graphs, Discrete applied mathematics, 92, 229-241, (1999) · Zbl 0930.05079
[19] Raman, V.; Saurabh, S., Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical computer science, 351, 3, 446-458, (2006) · Zbl 1086.68105
[20] Raman, V.; Saurabh, S.; Sikdar, S., Improved exact exponential algorithms for vertex bipartization and other problems, (), 375-389 · Zbl 1171.68646
[21] Reiter, R., A theory of diagnosis from first principles, Artificial intelligence, 32, 57-95, (1987) · Zbl 0643.68122
[22] A. Soleimanfallah, A. Yeo, A fixed parameter tractable algorithm for the 3-Hitting set problem and the feedback vertex set problem in tournaments, Preprint, 2008
[23] Wahlström, M., Exact algorithms for finding minimum transversals in rank-3 hypergraphs, Journal of algorithms, 51, 107-121, (2004) · Zbl 1091.68083
[24] M. Wahlström, Algorithms, Measures and Upper Bounds for Satisfiability and Related Problems, Ph.D. Thesis, Department of Computer and Information Science, Linköpings universitet, Sweden, 2007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.