CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

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

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
Discrete Optimization (1572-5286). Vol. 8 (2011), 1, p. 18-24.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: Hypergraph transversal, Vertex cover, Solution space, Parameterized algorithm



Denna post skapades 2011-03-16. Senast ändrad 2015-02-11.
CPL Pubid: 138021

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)