Graphes, Algorithmes et Réseaux
|
Archives année 2004-2005 |
Many graph
problems can be solved in linear time on graphs of bounded treewidth
with the strongest theoretical results in this direction obtained by
Bruno Courcelle in the late 80s. When considering the treewidth as a
parameter we obtain FPT algorithms. For the fastest algorithms we must
carefully design dynamic programming algorithms along a
tree-decomposition of the graph. Recently, several results have claimed
that faster algorithms can be obtained by instead using branchwidth and
so-called branch-decompositions. In this talk we will challenge this
claim. We first review the history of these algorithms, and present
semi-nice tree-decompositions that we claim combines the best
properties of nice tree-decompositions, branch-decompositions and in
fact also path-decompositions.
Nous nous intéressons aux propriétés des composantes connexes des graphes aléatoires, pour observer un phénomène connu sous le nom de «naissance de la composante géante». Aprés avoir donné des méthodes d'énumérations exactes sur les composantes connexes, nous étudions le nombre de création et la taille des composantes dominantes lors l'évolution du graphe aléatoire. Les différents résultats présentés ici sont obtenus en combinant des méthodes probabilistes aux méthodes asymptotiques issues de la combinatoire analytique.
Le problème que nous considérons est celui de l'entretien dynamique du réaliseur d'un graphe de permutation lorsque ce graphe est soumis à des modifications élémentaires de ses sommets et/ou de ses arêtes (ajout ou suppression). Notre approche est basée sur l'entretien dynamique de la décomposition modulaire du graphe de permutation considéré. L'algorithme que nous présentons procède à l'actualisation de la représentation adoptée (réaliseur + décomposition modulaire) en temps O(n) par opération. Nous montrons en quoi ce résultat de complexité est satisfaisant relativement à la représentation adoptée.
10 Mars 2005: VAG-APR
Parameterized Algorithms has in recent years evolved to become
an
effective tool for dealing with intractable NP-complete problems. For
some core NP-complete problems, i.e Vertex Cover, parameterized
algorithms are perhaps the most effective solution in practice, solving
instances of sizes up 10 000 vertices to optimality in reasonable time.
This talk will give a basic introduction to this field and
give
examples of the techniques, in particular bounded search tree and
kernalization, used to obtain parameterized algorithms. Vertex
cover will be used as an example throughout the talk.
Kleinberg a proposé un
modèle de graphes petit-mondes basé sur la grille. Sur ce
modèle le caractère petit-monde se traduit par
l'existence d'un algorithme glouton simple de routage efficace. La
longueur des chemins découverts est en moyenne O(logn.logn).
Cette performance est indépendante de la dimension d
grillesous-jacente. Nous montrons comment en augmentant
légèrement la mémoire disponible, la performance
peut-être améliorée en fonction de la dimension d.
Travail commun avec P. Fraigniaud
et C. Gavoille