Paper Info
Title
Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
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, [10]) 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.
Year
DOI
Venue
2011
10.1016/j.disopt.2010.02.006
Discrete Optimization
Keywords
Field
DocType
succinct representation,parameterized algorithm,double hypergraph dualization,vertex cover,hypergraph transversal,minimal vertex cover,solution space,h. fernau,shotgun proteomics,rank limitation,maximum minimal vertex,combinatorial aspect,fixed rank,earlier algorithm,protein inference problem,rank-2 case
Discrete mathematics,Graph,Combinatorics,Mathematical optimization,Inference,Constraint graph,Hypergraph,Transversal (geometry),Vertex cover,Mathematics,Parameterized algorithms
Journal
Volume
Issue
ISSN
8
1
Discrete Optimization
Citations 
PageRank 
References 
0
0.34
10
Authors
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99