Campus Event Calendar
Event Entry
What and Who
Some fixed-parameter tractable classes of hypergraph duality and related problems
Imran Rauf
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 4 June 2008
14:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
In this talk 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. Briefly, a parameterized problem with parameter k is fixed-parameter tractable if it can be solved by an algorithm running in time O(f(k)·poly(n)), where f is a function depending on k only, n is the size of the input, and poly(n) is any polynomial in n. The class FPT contains all fixed-parameter tractable 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.
Contact
Imran Rauf
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Hypergraphs; Frequent set; Fixed-parameter tractability
Imran Rauf, 05/26/2008 12:58
Imran Rauf, 05/26/2008 12:57 -- Created document.
Imran Rauf, 05/26/2008 12:57 -- Created document.