MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEPolynomial-time FPT algorithms
par Jan Arne Telle (Univ. of Bergen, Norway)
| Date : | 14/10/10 | | Time : | 10:30 | | Location : | Galois coriolis |
<pre>The runtime of an FPT algorithm can be specified by giving the values of
the
parameter k that would yield an algorithm with runtime polynomial in the
input size n.
For example, O(2^k + n) is polynomial for k in O(log n) and linear for k
up to log_2 n.
This viewpoint is prominent in combining recent results showing that:
1) a large class of domination-type problems in graphs are solvable in
O(2^{3k}poly(n)) time for parameter boolean-width (Bui-Xuan, Telle,
Vatshelle) and
2) a decomposition of boolean-width O(log n) can be computed in
polynomial-time
for various graph classes, like interval and permutation graphs
(Belmonte, Vatshelle).
In this talk we present results from the Master Thesis of Robert Sasak
comparing
17 graph parameters, with the aim of identifying candidates for similar
results.
</pre>
Page des séminaires
| 
