TY - GEN
T1 - Some fixed-parameter tractable classes of hypergraph duality and related problems
AU - Elbassioni, Khaled
AU - Hagen, Matthias
AU - Rauf, Imran
PY - 2008
Y1 - 2008
N2 - In this paper we present fixed-parameter algorithms for the problem Dual-given two hypergraphs, decide if one is the transversal hypergraph of the other-and related problems. In the first part, we consider the number of edges of the hypergraphs, the maximum degree of a vertex, and a vertex complementary degree as our parameters. In the second part, we use an Apriori approach to obtain FPT results for generating all maximal independent sets of a hypergraph, all minimal transversals of a hypergraph, and all maximal frequent sets where parameters bound the intersections or unions of edges.
AB - In this paper we present fixed-parameter algorithms for the problem Dual-given two hypergraphs, decide if one is the transversal hypergraph of the other-and related problems. In the first part, we consider the number of edges of the hypergraphs, the maximum degree of a vertex, and a vertex complementary degree as our parameters. In the second part, we use an Apriori approach to obtain FPT results for generating all maximal independent sets of a hypergraph, all minimal transversals of a hypergraph, and all maximal frequent sets where parameters bound the intersections or unions of edges.
UR - http://www.scopus.com/inward/record.url?scp=44649181228&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-79723-4_10
DO - 10.1007/978-3-540-79723-4_10
M3 - Conference contribution
AN - SCOPUS:44649181228
SN - 354079722X
SN - 9783540797227
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 91
EP - 102
BT - Parameterized and Exact Computation - Third International Workshop, IWPEC 2008, Proceedings
T2 - 3rd International Workshop on Parameterized and Exact Computation, IWPEC 2008
Y2 - 14 May 2008 through 16 May 2008
ER -