Parameterized Algorithms and Matroids: the use of representative sets

Postgraduate Thesis uoadl:1325895 322 Read counter

Unit:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Library of the School of Science
Deposit date:
2016-12-09
Year:
2016
Author:
Petropanagiotaki Maria
Supervisors info:
Θηλυκός Δημήτριος, Επίκουρος Καθηγητής Τμήματος Μαθηματικών, Ε.Κ.Π.Α.
Κολλίοπουλος Σταύρος, αναπληρωτής καθηγητής τμήματος Πληροφορικής και Τηλεπικοινωνιών
Κυρούσης Ελευθέριος, καθηγητής τμήματος Μαθηματικών, Ε.Κ.Π.Α.
Original Title:
Παραμετρικοί Αλγόριθμοι και Μητροειδή: η χρήση των συνόλων αντιπροσώπευσης
Languages:
Greek
Translated title:
Parameterized Algorithms and Matroids: the use of representative sets
Summary:
Let $M = (E, I)$ be a matroid and let $\mathcal{S} = {S_1, ... , S_t}$ be a family of subsets of $E$ of size $p$. A subfamily of $\mathcal{S}$ is said to be $q$-representative for $\mathcal{S}$ if some independent set in S can be extended to a larger independent set by $q$ new elements, then there is a set in subfamily that can be extended by the same $q$ elements. By the Two Families Theorem of Bollobás and its algebraic version by Lovász, there is a $q$-representative family with at most sets.
In this paper, we give two algorithms computing representative families. The first algorithm is about linear matroids and it turns Lovász ’s proof into an algorithm constructing a $q$-representative family in time bounded by a polynomial in $\binom{p+q}{p}$, $t$ and the time required for field operations. The second one is
about uniform matroids and computes a representative family in time $\mathcal{O}((1-x)^{-q} 2^{o(p+q)|} t logn)$.
We demonstrate how the efficient construction of representative families can be a powerful tool for designing parameterized algorithms for the following problems: ℓ-MATROID INTERSECTION, LONG DIRECTED CYCLE and k-PATH.
Main subject category:
Science
Keywords:
representative sets, parameterized algorithms, matroids, ℓ-MATROID INTERSECTION, LONG DIRECTED CYCLE, k-PATH
Index:
Yes
Number of index pages:
1
Contains images:
Yes
Number of references:
37
Number of pages:
57
representative sets.pdf (407 KB) Open in new window