Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover

Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover

0.00 Avg rating0 Votes
Article ID: iaor20112712
Volume: 8
Issue: 1
Start Page Number: 18
End Page Number: 24
Publication Date: Feb 2011
Journal: Discrete Optimization
Authors:
Keywords: combinatorial optimization, biology
Abstract:

Motivated by the need for succinct representations of all ‘small’ transversals (or hitting sets) of a hypergraph of fixed rank, we study the complexity of computing such a representation. Next, the existence of a minimal hitting set of at least a given size arises as a subproblem. We give one algorithm for hypergraphs of any fixed rank, and we largely improve an earlier algorithm (by H. Fernau, 2005, ) for the rank‐2 case, i.e., for computing a minimal vertex cover of at least a given size in a graph. We were led to these questions by combinatorial aspects of the protein inference problem in shotgun proteomics.

Reviews

Required fields are marked *. Your email address will not be published.