Graphes, Algorithmes et Réseaux
Groupe de Travail



Archives année 2004-2005


Retour à la page d'accueil du séminaire

???: VAG-APR
Jan Arne Telle, "Dynamic programming on tree-decompositions vs branch-decompositions"

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.

31 Mars 2005: VAG-APR
Anne-Elisabeth Baert "Evolution des grahes aléatoires : taille de la  composante dominante et double saut"

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.


24 Mars 2005: VAG-APR
Christophe Crespelle, "Décomposition modulaire et graphes de permutation dynamiques"

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
Christian Sloper, "Parameterized complexity for beginners talk"

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.  

Christian Sloper, is a phd-student from the Universty of Bergen, Norway, but is currently on a scholarship at Charles University, Prague.

16 Février 2005: FLUX
Olivier Gandouet, "The space complexity of approximating the frequency moments"

ainsi que deux 2 articles qui sont nommés dans celui-ci "some complexity questions related to distribued computing" et "lower bounds by probabilistic arguments".

Cet article ("The space complexity of approximating the frequency moment) démontre entre autres des bornes inférieures en espace sur l'approximation par comptage probabiliste des moments de fréquence d'un multi-ensemble (je rappelle que les moments de fréquence d'ordre k d'un multi-ensemble quelconque M est: $\sum_{i \in Supp(M)} M(i)^k ou M(i) est le nombre d'éléments de la classe i et supp(M) désigne le support de M). Les moments de fréquence ayant une grande importance dans l'analyse du multi- ensemble car ils permettent de répondre à des questions comme:
  •  les classes sont-elles équilibrées entre elles ?
  • si elles ne le sont pas quelle est la distribution qui s'en approche le plus ?
  • quelle est la classe dominante en nombre ?
Ils obtiennent des bornes en espace très légèrement sous linéaires en n
sur l'approximation de $F_k$ pour tout k (ou n est le cardinal du support
du multi-ensemble considéré). Ils arrivent à de jolis théorème en se servant d'un résultat sur $C_{\epsilon}$(f) ou $C_{\epsilon}$(f) une borne inférieur en nombre de communications entre 2 parties A et B qui possèdent chacun un vecteur v(A), v(B) de {O,1}^k et qui souhaitent en communiquant le minimum entre eux, calculer la valeur d'une fonction f(v(a),v(b)) à valeur dans {0,1} et ce avec une probabilité supérieur à $ 1-\epsilon$

16 Décembre 2004:
Emeric Gioan (U. Nice)

9 Décembre 2004: VAG-APR
Christophe Paul, Routage dans les réseaux de Kleinberg

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

2 Décembre 2004: VAG-APR-ARITH
Stéphan Thomassé (LaPCS), Construction de graphes denses sans triangles

25 Novembre 2004:

18 Novembre 2004:

11 Novembre 2004: Relâche

4 Novembre 2004: VAG-APR
Olivier Gandouet, Quelques propriétés des quadrangulations

28 0ctobre 2004: FLUX
  • Présentation générale du projet
  • Etude  de l'algorithme de comptage probabiliste LogLog: D'après l'article de M. Durand et P. Flajolet (ESA 03)

21 Octobre 2004: APR (Salle 1.4)
Alain Jean-Marie, Analyse probabiliste de l'utilisation de codes correcteurs d'erreurs dans les réseaux