Année 2004/2005

17 Septembre 2004

    Coloration acyclique par liste et méthodes probabilistes. Mickaël Montassier. 

    Résumé : Nous prouverons que si G est graphe de degré maximum Delta ne contenant pas de copie de K_{2, Gamma+1}, alors son nombre chromatique acylique par liste est inférieur à la partie supérieure de 9.sqrt(Gamma).Delta. La preuve est basée sur le Lemme Local de Lovasz. 

24 Septembre 2004

    Partition des arêtes d'un graphe planaire en deux planaires exterieurs. Daniel Gonçalves. 

    Résumé : nous montrerons que pour un graphe planaire G=(V,E), il existe une bipartition de E, E= A U B, telle que les graphes induits par chacune de ces parties, G[A] et G[B], soient des planaires exterieurs. Nous traiterons juste le cas des triangulations, les graphes planaires triangulés, car ce cas implique le cas général. Nous présenterons un algorithme qui partitionne chacune des composantes 4-connexes d'une triangulation T, de telle sorte que cela induise une partition correcte des arêtes de T. 

8 Octobre 2004

    Fano colourings of cubic graphs and the Fulkerson Conjecture. Edita Macajova. 

    Résumé : A Fano colouring is a colouring of the edges of a cubic graph by points of the Fano plane such that the colours of any three mutually adjacent edges form a line of the Fano plane. It has recently been shown by Holroyd and Skoviera (J. Combin. Theory Ser. B, to appear) that a cubic graph has a Fano colouring if and only if it is bridgeless. In this talk we show that six, and conjecture that four, lines of the Fano plane are sufficient to colour any bridgeless cubic graph. We establish connections of our conjecture to other conjectures concerning bridgeless cubic graphs, in particular to the well-known conjecture of Fulkerson about the existence of a double covering by 1-factors in every bridgeless cubic graph. 

15 Octobre 2004

    Dessin convexe des graphes plans triconnexes. Nicolas Bonichon. 

    Résumé : Un des challenges du dessin de graphe est de dessiner n'importe quel graphe planaire sur une grille (i.e. les sommets ont des coordonnées entières) la plus compacte possible. Dans le cas où le graphe est triconnexe, il est également possible (souhaitable) que les faces soient représentées par des polygones convexes. En collaboration avec Stefan Felsner (TU-Berlin) et Mohamed Mosbah, nous avons proposé un algorithme de dessin convexe sur des grilles de taille (n-2-Delta)*(n-2-Delta), où Delta est un paramètre du graphe (plus exactement du réaliseur minimal du graphe) variant de 0 à n/2-2. 

22 Octobre 2004

    Coloration orientée des graphes de Halin. Mohammad Hosseini. 

    Résumé : Un graphe de Halin H est un graphe planaire constitué d'un arbre T(H) ayant au moins trois feuilles et d'un cycle C(H) reliant de façon planaire l'ensemble des feuilles de T(H). Nous allons montrer que le nombre chromatique orienté de tout graphe de Halin est au plus 9 . 

29 Octobre 2004

    Largeur de branches des graphes d'intervalles circulaires. Frédéric Mazoit. 

    Résumé : Les décomposition en branches et la largeur de branches ont été introduites par Robertson et Seymour au début des années 90 pour étudier les décompositions arborescentes et la largeur arborescente. Bien que ces deux types de décompositions présentent des analogies, la largeur de branches possède des propriétés qui lui sont propres. Au cours de cet exposé, je présenterai de façon générale les décompositions en branches ainsi que certaines de leurs propriétés puis je montrerai comment calculer exactement la largeur de branches des graphes d'intervalles circulaires. 

5 Novembre 2004

    L(p, q)-Etiquetage sans trou. Fabrice Bazzaro. 

    Résumé : Le L(p, q)-étiquetage d'un graphe, est un étiquetage des sommets du graphe tel que deux sommets voisins doivent avoir leurs étiquettes distantes d'au moins p; deux sommets à distance deux doivent avoir leurs étiquettes à distance au moins q (en général, p >= q). Le L(p, q)-étiquetage sans trou est tel qu'entre la plus petite et la plus grande étiquette utilisée, toutes les étiquettes sont assignées à au moins un sommet. Nous nous intéressons au problème de décidabilité suivant : à partir d'un graphe G quelconque, quelle est la complexité de déterminer si G admet un L(p, q)-étiquetage sans trou ? 

19 Novembre 2004

    Cycle hamiltonien et couplages. Denise Amar.

    Travail commun avec Evelyne Flandrin (Orsay) et Grzegorz Gancarzewicz (Cracovie). 

    Résumé : On se place dans un graphe d'ordre n. Sigma_k(G) designe le minimum des sommes des degres de k sommets independants de G. Berman a resolu une conjecture d'Haggkvist et prouve le resultat suivant: TH: Si sigma_2(G)>=n+1, tout couplage dans G est contenu dans un cycle. On montre le resultat:
    1) Soit G 3-connexe d'ordre n, tel que sigma_3(G)>=2n et soit M un couplage dans G. S'il existe un cycle contenant toutes les aretes de M, alors il existe un cycle hamiltonien de G contenant les aretes de M.
    On en deduit:
    2) Si G est 3-connexe tel que sigma_2(G)>=n+1, sigma_3(G)>=2n, alors pour tout couplage M, il existe un cycle hamiltonien contenant toutes les aretes de M.
    Enfin on peut se passer de la condition sigma_2>=n+1 pour obtenir:
    3) Soit G 3-connexe, tel que sigma_3 >=2n et soit M un couplage dans G sans coupe impaire. Il existe dans G un cycle hamiltonien contenant toutes les aretes de M. 

26 Novembre 2004

    Partition des arêtes des graphes toriques et applications. Arnaud Labourel. 

    Résumé : Avec l'aide de Cyril Gavoille et Nicolas Bonichon, j'ai cherché à étendre la décomposition en 3 arbres des triangulations planaires connue sous le nom de réalizer aux graphes toriques. On a réussi à prouver le théorème suivant:
    Il est possible de trouver 3 arêtes dans tous les graphes toriques telles que enlevées le graphe soit d'arboricité 3, c'est-à-dire décomposable en trois forêts.
    La preuve est constructive, elle donne un algorithme qui donne les trois arêtes à enlever ainsi que les trois forêts. Je parlerai des applications de ce résultat pour les graphes universels et les schémas d'adjacence compact. Je parlerai aussi des autres partitions d'arêtes connues pour les graphes planaires et toriques. 

3 Décembre 2004

    Arc-coloration de digraphes et fonction d'image disjointe. Frédéric Havet. 

    Résumé : Soit f et g deux applications d'un ensemble fini E dans un ensemble F d'images disjointes, i.e. f(x) \neq g(x) pour tout x. On cherche à partitionner E en un nombre minimum de sous-ensembles E_i tels que f(E_i) et g(E_i) ne s'intersectent pas. Nous verrons que ce problème se transforme en un problème d'arc-coloration de digraphe. Une arc-coloration des arcs est une coloration des arcs d'un digraphe telle que un arc uv et un arc vw aient des couleurs différentes. Mais uv et wv peuvent être colorés de même manière. Nous donnerons ensuite quelques résultats. 

10 Décembre 2004

    Quelques résultats de NP-complétude. Pascal Ochem. 

    Résumé : Nous considèrerons differents types de colorations impropres. Nous montrerons la NP-complétude de chaque coloration pour une classe de graphes planaires aussi restreinte que possible (biparti, grande maille, petit degre... ). 

7 Janvier 2005

    Les flots antisymétriques. André Raspaud. 

14 Janvier 2005

    Volumes of 3D drawings of graphs. Lubomir Torok (with Imrich Vrto). 

    Résumé : The considered 3D drawings of graphs are motivated mainly by 3D VLSI design. Vertices of the graph are mapped into the 3D grid and edges are drawn as the grid edge disjoint paths. Edges can cross but not overlap. We study 3-dimensional layouts of the hypercube in 1-active layer and general model. We provide general lower bounds for both models based on cutwidth of the graph. We show an optimal constructions for hypercube. Finally, we discuss the generalization of these constructions for both models and provide the asymptotically optimal results for some homogenous products of known interconnection networks, such as Butterfly, CCC, star graph, de Bruijn and others. This part is analogue of a similar work done by Fernandez and Efe for 2D drawings using a different approach. 

21 Janvier 2005

    Ratio d'imperfection des graphes circulaires parfaits. Sylvain Coulonges. 

    Résumé : Un graphe G est parfait ssi tout sous graphe induit H est tel que sa taille de clique est égale à son nombre chromatique. On peut écrire cette propriété sous forme de morphisme de graphe conservant les arêtes : un graphe est parfait ssi il existe, pour tout sous graphe induit H, un entier n tel qu'il existe des morphismes
    K_n -> H -> K_n

    Posons K_k/d avec k>=2d le graphe avec k sommets 0,...,k-1 et l'ensemble d'arêtes {ij | d <= |i-j| <= k-d}. On dit qu'un graphe G est circulaire parfait (introduit par Xuding Zhu) ssi pour tout sous graphe induit H, il existe k et d tel qu'il existe des morphismes
    K_k/d -> H -> K_k/d

    Nous allons explorer cette classe de graphe en étudiant leurs ratios d'imperfection, notion introduite par Gerke et McDiarmid en 2001. 

11 Février 2005

    Session de Problèmes. Arnaud Labourel, Daniel Gonçalves, Mickaël Montassier. 

18 Février 2005

    On the chromatic number of distance graphs. Javier Barajas. 

4 Mars 2005

    Routage simple-source. Cyril Gavoille. 

    Résumé : Je vous parlerais d'un problème de routage depuis la racine d'un arbre dans le cas où les adresses des sommets sont arbitraires. Au programme: table de routage, facteur d'étirement, latence, fonction de hachage, parcours en profondeur, logn, etc. 

11 Mars 2005

    Sur les graphes fortement circulaire-parfaits, sans triangles. Arnaud Pêcher. 

    Résumé : Un graphe est dit "fortement circulaire-parfait" s'il est circulaire parfait et son complémentaire également. Nous donnons une caractérisation des graphes fortement circulaire-parfaits, sans triangles. Celle-ci permet de:
    * donner un algorithme de reconnaissance en temps polynomial
    * montrer que ces graphes sont t-parfaits: en particulier, le calcul d'un stable maximum (version pondérée) se fait en temps polynomial 

18 Mars 2005

    Coloration acyclique par listes des graphes de petit degré maximal. Daniel Gonçalves. 

    Résumé : Nous prouverons que tout graphe ayant un degré maximal au plus 3 est acycliquement 4-liste coloriable et que tout graphe ayant un degré maximal au plus 4 est acycliquement 5-liste coloriable. 

1 Avril 2005

    The Shortest Cycle Cover: a survey and new trends. André Raspaud. 

    Résumé : A cycle cover of a graph G is a family of cycles such that every edge of G is contained in at least one cycle of the family. The length of the cycle cover is the sum of the lengths of its cycles. The problem is to find a bounds for the length of a shortest cycle cover for any bridgeless graph. We give here a little survey of the known results end the relationship with the nowhere zero flows, the circular flows and the cycle double covers. 

8 Avril 2005

    Codage d'une triangulation à l'aide de mots de piles. Nicolas Bonichon. 

    Résumé : Dans sa thèse Olivier Guibert considére, entre autre, les mots composés de 3 lettres '1', '2' et '3' tels que tout préfixe possède plus de '1' que de '2' et plus de '2' que de '3'.Il établit un certain nombre de bijections entre des familles d'objets combinatoires variés et des mots de piles dont certains motifs sont exclus. Par ailleurs il conjecture qu'en excluant cerains motifs (-2Y2-33 ou -1Y3-22), ces mots sont comptés de la même manière que les triangulations du plan. Dans le but de coder efficacement les triangulations, nous donnerons une bijection entre les triangulations et les mots de piles qui excluent le motif -2Y2-31. 

15 Avril 2005

    Peut-on transformer tout graphe en petit-monde ? Nicolas Hanusse. 

    Résumé : Un graphe est un petit-monde navigable si un algorithme glouton décentralisé (chaque sommet n'a qu'une connaissance partielle du graphe) permet de faire un routage en un nombre polylogarithmique de sauts. L'immense majorité des graphes ne possède pas cette propriété. Est-il possible de modifier légèrement un graphe pour le rendre petit-monde et navigable ? Nous introduisons une opération d'augmentation de graphes qui permet de rendre petit-monde navigable les graphes dont les boules ont une croissance modérée. 

22 Avril 2005

    Peut-on transformer tout graphe en petit-monde ? Nicolas Hanusse. 

    Résumé : suite et fin. 

29 Avril 2005

    Partition de graphes en stables et en cliques. Pascal Ochem. 

    Résumé : Soit G un graphe simple à n=|V(G)| sommets. Notons F(G) l'ensemble des couples (S,C) de N² tels que G n'a pas de partition en S stables et en C cliques. On étudiera la taille f(G)=|F(G)| de cet ensemble. On donnera les valeurs minimales et maximales de f(G) en fonction de n pour les graphes simples en general ainsi que pour quelques classes de graphes parfaits. On conjecture que si G est parfait, alors f(G) <= n. 

20 Mai 2005

    Proof Labeling Schemes. Amos Korman. 

    Résumé : The main topic of the talk is local verification of global properties. Several natural questions are addressed, such as ``how expensive is local verification? and more specifically ``how expensive is local verification compared to computation?. A suitable model is introduced in which these questions are studied in terms of the number of bits a node needs to communicate. In particular, it is shown that the cost of verification is sometimes rather high, even higher than the number of bits needed for a computation. On the other hand, approaches are presented for the efficient construction of schemes, and upper and lower bounds are established on the cost of schemes for multiple basic problems. We will also disscuss the role and cost of unique identities in terms of impossibility and complexity. 

17 Juin 2005

    Searching for Black Holes in (semi-)synchronous networks.
    Fabiano Sarracco (Università di Roma, "La Sapienza").
    Joint work with Ralf Klasing, Euripides Markou and Tomasz Radzik. 

    Résumé : A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. In this talk, I shall present and discuss the problem of locating all the black holes in a network, by using a set of mobile agents. I will briefly present a first model introduced by S. Dobrev, P. Flocchini, G. Prencipe, and N. Santoro (DISC 2001), and show the main results for this model. A paper by J. Czyzowicz, D. Kowalski, E. Markou, and A. Pelc (OPODIS 2004) introduces a new model in which the network is (semi-)synchronous, there is at most one black hole in the network and the search is performed by only two agents. For this model, we showed (SIROCCO 2005) the NP-hardness of the problem in arbitrary networks, and presented a 7/2-approximation algorithm. Future research directions will be indicated. 

24 Juin 2005

    Une nouvelle preuve du théorème des quatre couleurs. Georges Gonthier (Inria/Microsoft). 

24 Juin 2005

    Selective families of sets and their applications in communication algorithms in ad-hoc radio networks.
    Tomasz Radzik (Department of Computer Science, King's College London).
    Joint work with B. Chlebus, L. Gasieniec, R. Klasing, D. Kowalski and Q. Xin. 

    Résumé : A family F of subsets of set [N] = {1,2,...,N} is "k-selective" (or a "k-selector") if for every non-empty subset X of [N] of size at most k, there is a set B in F which has exactly one element in common with X. The notion of selective families, and its variations, is the main tool in constructions of deterministic communication protocols for "radio networks" with unknown topology. We show in this talk how selective families are used in the currently fastest deterministic protocols for the bradcasting, gossiping and wake-up problems in such networks. We also discuss explicit constructions of the variations of selective families required in those protocols. 

1 Juillet 2005

    Minimum cycle factors in Quasi-Transitive Digraphs. Jorgen Bang-Jensen.

Année 2003/2004

26 Septembre 2003

    Colorations totales. André Raspaud. 

    Résumé : Rappels et présentation du (d,1)-total coloring 

3 octobre 2003

    (d,1)-total coloring. Fabrice Bazzaro. 

    Résumé : Une (d,1)-totale coloration est une coloration des arêtes et des sommets telle que la coloration des arêtes soit propre, la coloration de sommets soit propre et que la différence entre la couleur d'un sommet et de ses arêtes incidentes soit au moins d. Nous nous intéresserons aux familles de graphes classiques mais également aux graphes planaires avec une grande maille. Nous ferons intervenir des procédures de déchargement. 

17 octobre 2003

    (d,1)-total coloring. Mickaël Montassier. 

    Résumé : Nous nous intéresserons à la (d,1)-totale coloration de graphes en fonction de leur Mad (maximum average degree). 

21 octobre 2003

    Coloration orientée. Pascal Ochem. 

    Résumé : Nous nous intéresserons au nombre chromatique orienté maximal des graphes planaires sans triangle. On montrera que cette constante est comprise entre 11 et 59. 

7 Novembre 2003

    Decomposition, Enumération et Génération de cartes planaires extèrieures. Nicolas Hanusse. 

    Résumé : Nous montrons une décomposition des cartes planaires extèrieures en 1 arbre et un ensemble d'arêtes non apparentées. Nous en déduisons:

        * une bijection entre cartes planaires extèrieures et arbres bicoloriés
        * une asymptotique du nombre de cartes planaires extèrieures
        * un codage optimal permettant requêtes d'adjacence en temps constant
        * un algorithme linéaire de génération aléatoire uniforme
        * de jolis dessins ... 

14 Novembre 2003

    Promenade dans le monde merveilleux des graphes circulaires parfaits. Arnaud Pecher. 

21 Novembre 2003

    Optimisation du débit pour quelques communications collectives sur plateforme hétérogène. Olivier Beaumont. 

    Résumé : Nous nous interesserons à la diffusion d'un message à l'ensemble des noeuds d'une plateforme hétérogène (au niveau de la vitesse des liens de communication). Nous cherchons à maximiser le débit d'une telle opération de diffusion , en supposant que la taille du message à diffuser est grande. Nous montrerons comment calculer le débit optimal et comment construire un ordonnancement périodique qui réalise (asymptotiquement) ce débit. 

28 Novembre 2003

    Optimisation du débit pour quelques communications collectives sur plateforme hétérogène (suite et fin). Olivier Beaumont. 

9 Janvier 2004

    Bicycles et Tas de Sable. Robert Cori. 

16 Janvier 2004

    Diffusion dans le modèle rendez-vous. Nicolas Hanusse. 

    Résumé : nous proposons un modèle de communication basé sur les rendez-vous et nous analysons le temps de diffusion d'un algorithme probabiliste, multi-saut, distribué, synchrone pour différentes topologies. 

30 Janvier 2004

    "chi-binding functions". M. A. Shalu. 

    Résumé : ps 

6 Février 2004

    Diffusion dans le modèle rendez-vous (suite et fin). Nicolas Hanusse. 

13 Février 2004

    Routage avec indépendance des noms. Cyril Gavoille 

    Résumé : Cet exposé assez général survole plusieurs articles sur les schémas de routage. En particulier il présente les relations entre l'évolution du graphe inter-domaine d'Internet et le facteur d'étirement moyen dans le schéma de Thorup et Zwick. Puis j'aborderai plus en détails le problème du routage avec "indépendance des noms" qui consiste à optimiser les tables de routage sans renuméroter les sommets du graphes, spécificités qui prend son importance dans la problématique des réseaux Pair-à-pair. 

20 Février 2004

    Routage avec indépendance des noms (suite et fin). Cyril Gavoille 

5 Mars 2004

    Coloration acyclique par liste. Mickaël Montassier. 

    Résumé : Après avoir fait un bref rappel sur les notions de coloration acyclique et coloration par liste, nous présenterons la coloration acyclique par liste ainsi que quelques résultats et conjectures. Nous nous intéresserons plus particulièrement à la coloration acyclique par liste des graphes ayant un degré moyen maximal strictement inférieur à 10/3. Nous ferons intervenir des proporiétés locales et une procédure de déchargement. 

12 Mars 2004

    Utilisation de propriétés structurelles de certaines classes de graphes pour des constructions logiques. Bruno Courcelle.

    Résumé : Une conjecture de D. Seese énonce que si un ensemble de graphes a une théorie monadique du second-ordre décidable, il a une "structure arborescente". On peut montrer que cette conjecture est vraie si et seulement si elle est vraie pour l'une de ces classes :

        * les graphes orientés sans circuits,
        * les ordres partiels,
        * les "split graphs",
        * les graphes de comparabilité. 


    Elle peut être prouvée pour les graphes uniformément k-creux (donc les planaires et les graphes de degré borné), les "line graphs" les graphes d intervalles, les ordres partiels de dimension 2, les ordres Quasi-Série-Parallèle, les graphes ayant "peu de cliques".
    Les méthodes utilisées ont des limites qu'un argument de comptage permet de montrer. 

19 Mars 2004

    The Strong Perfect Graph Theorem and consequences for recognizing perfect graphs. Anne Wagler 

    Résumé : A graph is called perfect if, for each of its induced subgraphs, the clique number equals the chromatic number. A famous conjecture of Claude Berge claims that a graph is perfect if and only if it does not contain any odd hole or odd antihole as induced subgtraph. This conjecture has been verified in 2002 by Chudnovsky, Robertson, Seymour, and Thomas. A consequence is that the recognition problem of perfect graph can be solved by recognizing odd hole- and odd antihole-free graphs. 

26 Mars 2004

    Étoile-coloration dirigée acircuitique. Alexandre Pinlou 

    Résumé : Après avoir défini les notions d'arc-coloration orientée et d'étoile-coloration dirigée acircuitique, je commencerai par montrer rapidement une relation qui permet de passer de l'une à l'autre. Je montrerai ensuite de façon plus détaillée que les graphes de degré au plus trois admettent une 4-étoile-coloration dirigée acircutique. 

14 Mai 2004

    Circulaire imperfection des graphes partitionnables. Arnaud Pêcher 

4 Juin 2004

    Some new and old Conjectures in Edge-Coloring. David Coriolaro.

    Résumé : We will present and discuss some new and old problems and conjectures in edge-coloring. 

11 Juin 2004

    Différents types d'arboricité. Pascal Ochem.

    Résumé : Nous redéfinissons l'arboricité, l'arboricité linéaire, l'arboricité etoile, l'arboricité "caterpillar", (et d'autres) dans un cadre unifié. Nous donnerons des bornes inferieures pour ces arboricités et repondrons à un probleme ouvert de Kostochka et West. 

18 Juin 2004

    Interval Routing in Random Graphs. Martin Nehez.

    Résumé : Interval routing is a space-efficient routing method. From a graph-theoretic point of view, it is a graph-labeling problem according to given complexity measures. Mostly, the complexity measures such as the number of interval per outgoing edges and stretch of routing paths were studied. The talk will concern interval routing in random graphs. Several recent results, proving techniques and open problems will be discussed.

Année 2002/2003

20 Septembre 2002 Francesc Comellas de l'Université Polytechnique de Catalogne (Barcelone - Espagne)

    Deterministic small-word communication networks. 

4 Octobre 2002 Arnaud Pecher

    Nombre circulaire chromatique des graphes partitionnables 

    Résumé : dans l'étude de Zhu sur les colorations circulaires (2001), il est rappelé qu'il n'est connu qu'un seul graphe circulant "étoile-extremal" avec un nombre premier de sommets. En collaboration avec A. Galluccio (IASI -CNR, Rome), nous en avons exhibé une infinité, en cherchant à calculer le nombre circulaire chromatique des graphes partitionnables. 

11 Octobre 2002 Nicolas Hanusse

    Algorithme probabiliste de recherche par agent mobile dans un réseau avec menteurs.

18 Octobre 2002 Nicolas Hanusse

    Algorithme probabiliste de recherche par agent mobile dans un réseau avec menteurs. (suite et fin)

25 Octobre 2002 Relâche

1er Novembre 2002 Relâche (Toussaint)

8 Novembre 2002 Eric Sopena

    Colorations d'incidences

15 Novembre 2002 Noël Novelli

    Utilisation de graphes et treillis pour le Data Mining (introduction)

22 Novembre 2002 Noël Novelli (suite)

    Utilisation de graphes et treillis pour le Data Mining (introduction)

29 Novembre 2002 Denise Amar

    Cyclabilite d'un couplage dans les graphes bipartis

6 Décembre 2002 Journée "algorithmique des grands graphes"

    * Christophe Paul (LIRMM) : Clustering.
    * Guillaume Fertin (IRIN) : Proposition d'un modèle déterministe de réseaux petit monde sans échelle.
    * Laurent Viennot (INRIA) : Réflexion sur la définition du graphe du Web. 11h30-12h :
    * Nicolas Shabanel (LIP) : Modéliser les graphes physiques d'internet.
    * Matthieu Latapy (LIAFA) : Quelques gros graphes particuliers: graphe petit monde, graphe d'internet et graphe du Web.
    * Cyril Gavoille (LaBRI) : Le plus petit ancêtre commun.
    * Julien Moncel (Leibniz) : Codes identifiants.
    * Pierre Fraigniaud (LRI) : Recherche dans les graphes et applications. 

13 Décembre 2002 Olivier Togni

    Multicolorations et routage optique

    Résumé : On s'intéresse au problème de coloration des chemins dans un graphe orienté symetrique, en relation avec le routage WDM. Dans ce cadre, nous définissons une nouvelle modélisation du problème sous forme de multicoloration de graphe. Celle ci nous permet de trouver de nouveaux résultats pour certains types de routages et de redémontrer des résultats existants d'une autre manière.
    Nous présentons, en particulier, des résultats sur la coloration des chemins ligne-colonne dans la grille et la coloration des chemins dans le H-graphe.

17 Janvier 2003 André Raspaud

    Colorations circulaires et Colorations fractionnaires

24 Janvier 2003 David Renault

    Enumération de graphes sommet-transitif planaires localement finis. 

31 Janvier 2003 Fabrice Bazzaro

    Caractérisation des graphes de permutation. 

7 Février 2003 Xuding Zhu (Department of Applied Mathematics National Sun Yat-sen University, Taiwan, ROC.)

    The circular chromatic number of subgraphs 

    Résumé : This talk discusses the following problems:

       1. how much could be the decrease of the circular chromatic number by deleting an edge ?
       2. how much could be the decrease of the ciruclar chromatic number by deleting a vertex ? 

    A few results will be presented, and a few questions will be asked. 

14 Février 2003 Arnaud Pecher

    A propos de webs qui ne sont pas 'rang-parfaits' 

21 Février 2003 Vacances

28 Février 2003 Guillaume Fertin (IRIN, Nantes)

    Caractérisation des Génomes à Distance Synténique Maximale (avec Cédric Chauve, LaCIM, Montréal)

    Résumé : Un génome G1 se modélise sous la forme G1={S1,S2 ... Sm}, où chaque Si est un chromosome, c'est-à-dire un ensemble de gènes choisis dans {g1,g2 ... gN}.
    La distance synténique entre deux génomes G1 et G2 est définie comme le nombre minimum d'opérations permettant de passer de l'un à l'autre, où les 3 opérations autorisées, issues des observations des biologistes, sont les suivantes:

        * fusion : deux chromosomes fusionnent pour n'en former qu'un
        * fission : un chromosome se partitionne en deux chromosomes
        * translocation : deux chromosomes échangent des sous-ensembles de leurs gènes 

    Il a été démontré que la plus grande distance possible existant entre deux génomes à (respectivement) m et n chromosomes est égale à m+n-4.
    Dans cet exposé, nous poursuivons cette étude en répondant à une question ouverte de Kleinberg et Liben-Nowell sur la caractérisation des instances représentant des génomes à distance synténique maximale (c'est-à-dire, m+n-4) l'un de l'autre.
    Ce résultat repose entre autres sur une propriété démontrant l'équivalence entre la translocation et un problème étudié depuis longtemps dans le domaine des réseaux d'interconnexion : le "gossiping". 

7 Mars 2003 Matthew Newton et Mark Withall de l'Université Loughborough (UK).

    "Edge Crossing Minimisation of Two-Layer Bipartite Graphs"

    "Minimisation de croisements d'arêtes des graphes bipartis sur deux couches" 

    Abstract : We introduce the problem of edge crossing minimisation of two-layer bipartite graphs. We present a comparison of previous heuristics and a selection of new methods. 

    Résumé : Nous présentons le problème de la minimisation de croisements d'arêtes des graphes bipartis sur deux couches. Nous présentons une comparaison d'heuristiques existantes et d'une selection de nouvelles méthodes. 

28 Mars 2003 Mickaël Montassier

    Observabilité des arbres récursifs de cliques. 

    Résumé : Une coloration d'arêtes est dite :

        * propre, si deux arêtes incidentes à un même sommet ont des couleurs différentes.
        * sommet-distingué, si quelle que soit la paire de sommets u, v, l'ensemble de couleurs des arêtes incidentes à u est différent de l'ensemble de couleurs des arêtes incidentes à v. 

    L'observabilité d'un graphe G est le nombre minimal de couleurs permettant d'avoir une coloration propre sommet-distingué des arêtes de G.

    Arbres récursifs de cliques - définition :

        * t=0, K(q,t) est une q-clique.
        * pour t>=1, K(q,t) est construit à partir de K(q,t-1) dans lequel pour chaque sous-graphe H isomorphe à une q-clique, un nouveau sommet est ajouté et joint à tous les sommets de H. 

    Nous allons déterminer l'observabilité des arbres réursifs de cliques. 

25 Avril 2003 Pascal Ochem

    Coloration acyclique impropre des graphes planaires 

    Résumé : Une coloration des sommets est dite:

        * propre si le sous-graphe induit par des sommets de meme couleur est un stable.
        * acyclique si pour tout couple (x,y) de couleurs, les aretes incidentes à un sommet x et un sommets y induisent une foret. 

    Pour une coloration impropre, on se donne une classe de graphe F_i pour chaque couleur i, et il faut que le sous-graphe induit par les sommets de couleur i appartienne à F_i.

    Je donnerai un (ou deux) résultat négatif concernant la coloration acyclique impropre des graphes planaires avec 2 couleurs. 

2 Mai 2003 Yon Dourisboure

    Longueur arborescente des graphes. 

    Résumé :

        * Je donnerais les définitions de décomposition arborescente, largeur arborescente et longueur arborescente.
        * Puis nous montrerons que tout graphe G, planaire extérieur, admet une décomposition arborescente de largeur 2 et de longueur Chord(G)/3. De plus cette décomposition est optimale pour les deux paramètres. 

9 Mai 2003 Yon Dourisboure

    Longueur arborescente des graphes (suite). 

    Résumé : Après quelques rappels, nous répondrons à une question posée la semaine dernière : "Est-ce que tout graphe admet une décomposition arborescente de longueur et de largeur optimale ?". 

16 Mai 2003 Mohammad Hosseini

    La coloration incidence des graphes k-dégénérés 

23 Mai 2003 Olivier Baudon

    une heuristique pour le problème de l'arrangement linéaire 

    Résumé : On considère un graphe non orienté G = (V,E) avec une valuation des arêtes w.

    Il s'agit de trouver une permutation Pi des sommets minimisant somme{|Pi(j)-Pi(i)| * w(i,j); (i,j) de E}. 

13 Juin 2003 Mohammad Hosseini

    La coloration incidence des graphes k-dégénérés (suite) 

20 Juin 2003 Cyril Gavoille

    matrice de distances universelle 

    Résumé : Etant donnée une famille de graphes F et un entier n, une matrice de distances universelle pour F est une matrice carrée M(n) telle que la matrice de distance de tout graphe à n sommets de F soit une sous-matrice de M(n). Par exemple pour n=4 et pour F={graphes connexes} (dessinés ci-dessous) on peut vérifier que F possède une matrice de distance universelle de dimension 7.

    (Exercice pour vendredi ?)

        o--o   o--o--o      o     o      o--o      o 
        |         |        /|    /|\     |  |     /|\   (K_4 en ascii
     o--o         o    o--o-o   o-o-o    o--o    o-o-o   c'est dur !)
                                                  \_/

    (aide: il suffit de considérer la matrice des distances d'un graphe à 7 sommets qui "contient" chacun des graphes ci-dessus. "Contenir" veut dire ici que les distances dans les sous-graphes doivent correspondre aux distances du sur-graphe).

    Je vous montrerai que la famille des graphes d'intervalles possède une matrice de distance universelle de dimension O(n^5) et donc un étiquetage de distance avec des étiquettes de 5logn bits (Ah bon ?!? c'est quoi le raport ?), et que toute matrice de distance universelle pour cette même famille est de dimension au moins n^3/(logn)^4 (ça c'est si j'ai le temps). 

27 Juin 2003 Edita Ricanyova

    Flow number of snarks 

11 Juillet 2003 Daniel Goncalves

    Caterpillar arboricity of planar graphs 

    Résumé : The arboricity a(G) of a graph is defined to be the minimum number of forests containing all the edges of G. In a similar way, the linear arboricity la(G) (resp. star arboricity sa(G), caterpillar arboricity ca(G)) of G is the smallest number of forests containing all the edges of G such that each component of each forest is a path (resp. a star, a caterpillar). A star is a tree where all the edges are adjacent to a vertex of degree 1. A caterpillar is a tree with the property that removal of all the end vertices and the edges containing them yields a path.

    We will prove that ca(G) < 5 for all planar graph G.

Année 2001/2002

21 Septembre 2001 Bernard Mans, Dept. of Computing, Macquarie University, Sydney, Australia

    Bisecting and Gossiping in Circulant Graphs (en Francais "Bisection et Gossip dans les graphes circulants") 

    Résumé : Circulant graphs are regular graphs; they include network toplogies such as rings, complete graphs, distributed loops, and chordal rings. The bisection width of a network topology is an important factor for determining the complexity of distributed algorithms in which information has to be exchanged between two subsets of the networks. We give upper bounds on the vertex-bisection (respectively the edge-bisection) width of these graphs. Moreover, our method provides a polynomial algorithm to partition the set of vertices (respectively the set of edges) to obtain these bounds and the respective sets. For different communication models, we introduce new algorithms and give matching lower and upper bounds of the number of rounds required to solve the gossip problem.

    These show that, for circulant graphs, a simple condition for isomorphism, combined with lattices reduction algorithms, can be used to develop optimal distributed algorithms.

    This is a join work with Igor Shparlinski 

28 Septembre 2001 André Raspaud

    Sur les fonctions cycle (tension)-continues dans les graphes et les pré-ordres dérivés. 

    Résumé : Certaines des conjectures fortes dans la theorie structurelle des graphes ont une connotation fortement algébrique. En autres les conjectures de Tutte sur les flots, les polynômes asoociés à des phénomènes combinatoires, la conjecture d'Hedetniemi sur le produit de graphes, et la conjecture d'Ulam sur la reconstruction. Les meiileurs résultats ont été obtenus aprés avoir réalisé un contexte algèbrique. Il n'est pas surprenant que plusieurs de ces conjectures peuvent être exprimés en termes d'ordres partiels. Nous étudions des ordres dans les graphes liés aux structures algèbrique des flots et tensions. Notre approche utilise des applications définies par des conditions de continuité. Notre motivation est l'étude des problèmes de flots et de coloration. De plus nous prouvons qu'un homomorphisme est juste une application tension continue. 

5 Octobre 2001 Cyril Gavoille

    Un "étiquetage de direction" dans les arbres (1/2). 

    Résumé : On considère le problème d'étiqueter les sommets d'un arbre par des mots binaires (les plus courts possible) de sorte qu'il existe une fonction f, dit fonction de routage, qui à tout couple d'étiquettes (L(x),L(y)) issu d'un arbre T associe p=f(L(x),L(y)) tel que p soit le numéro local en x de l'arête (x,z) (c'est-à-dire un unique entier compris entre 1 et deg(x)) et z soit situé sur le plus court chemin de x à y dans T.

    Je montrerai qu'il est possible d'obtenir un tel étiquetage avec des mots de longueur (logn)^2/(4loglogn) bits, où n est le nombre de sommets de l'arbre. Dans la séance suivante, je montrerai une borne inférieure sur cette longueur en (logn)^2/(7loglogn) bits.

    Ce travail est en collaboration avec Pierre Fraigniaud du LRI. 

12 Octobre 2001 Cyril Gavoille

    Un "étiquetage de direction" dans les arbres (suite et fin). 

    Résumé : Cet exposé fera suite à l'exposé de la semaine précédente. Je montrerai qu'il n'est pas possible d'obtenir un étiquetage de direction avec des mots de longueur inférieur à (logn)^2/(7loglogn) bits, où n est le nombre de sommets de l'arbre. Il n'est pas nécessaire d'avoir suivi la séance précédente. Je ferai quelques rappels en début de séance. 

19 Octobre 2001 Yon Dourisboure

    Routage dans les graphes triangulés. 

26 Octobre 2001 Yon Dourisboure

    Routage dans les graphes triangulés. (suite et fin) 

2 Novembre 2001 Relâche

9 Novembre 2001 Fabrice Bazzaro

    Algorithme dynamique de reconnaissance de graphes de permutation. 

    Résumé : Ce travail est base sur un article de Corneil Perl et Stewart de 85 proposant un algorithme dynamique de reconnaissance des cographes. Il s'agit d'utiliser la decomposition modulaire afin de voir dans le co-arbre quelles sont les proprietes permettant l'ajout et ensuite de donner une mise a jour de l'arbre.

    La presentation se basera essentiellement sur les noeuds premiers d'une telle decomposition et l'objectif est le suivant : On a un graphe de permutation G=(V,E), est-il posssible d'ajouter un sommet x de voisinage N(x) C V(G) pour que le graphe reste un graphe de permutation et si oui comment mettre a jour la structure de donnee utilisee. 

16 Novembre 2001 Olivier Baudon

    Les P-Q arbres 

    Résumé : L'exposé sera un cours sur les PQ-arbres :

        * structure de données
        * utilisation
        * algorithmes 

23 Novembre 2001 Olivier Baudon

    Les P-Q arbres (suite et fin) 

30 Novembre 2001 Relâche

7 Décembre 2001 Jana Maxova (Université Charles de Prague)

    The Cycle Double Cover Conjecture and Related Topics 

    Résumé : The CDC conjecture states that for every bridgeless graph G, there exists a family of cycles in G, such that every edge of G appears in exactly two of them. In the talk I will review some results related to this topic.
    I will mostly focus on oriented version of the above mentioned problem. 

14 Décembre 2001 Nicolas Bonichon

    Réaliseurs : flips diagonaux et mots de Dyck 

    Résumé : Les arbres de Schnyder ont été introduits par Walter Schnyder en 1989. Ces triplets arbres, ou réaliseurs, sont à la base de nombreux algorithmes de dessins de graphe.
    Nous présenterons deux propriétés :

        * On peut transformer un réaliseur de taille n en tout autre réaliseur de taille n uniquement à l'aide de flips diagonaux.
        * Un réaliseur peut être codé à l'aide de 2 mots de Dyck qui ne se croisent pas. 

    Cet exposé reprend les résultats présentés aux Groupes de travail "Graphes et Logique" du lundi 22 octobre et "Combinatoire Énumérative et Génération Aléatoire" du vendredi 19 octobre. 

28 Décembre 2001 Vacances

4 Janvier 2002 Vacances

11 Janvier 2002 Nicolas Hanusse

    Algorithmes déterministes de recherche d'informations par agents mobiles dans un réseaux avec menteurs (1/2). 

    Résumé : Un agent mobile est un programme naviguant dans un réseau pour une tâche spécifique: rappel automatique de rendez-vous, composition de numéros de téléphone, recherche d'informations, ... Je m'intéresse a un modèle pour la recherche d'informations.
    Dans ce modèle, tous les noeuds du réseau indiquent un chemin à suivre pour aller à la destination. Il peut arriver que certains noeuds, défaillants ou pas-à-jour, indiquent un mauvais chemin. En supposant borné le nombre de sommets défaillants nommés menteurs, je m'interesse à différents algorithmes déterministes de recherche qui prennent en considération la topologie. 

18 Janvier 2002 Nicolas Hanusse

    Algorithmes déterministes de recherche d'informations par agents mobiles dans un réseaux avec menteurs (2/2). 

25 Janvier 2002 Olivier Baudon

    Tree spanners. 

    Résumé : Cet exposé est une présentation de l'article de Cai et Corniel, "Tree spanners", SIAM J. of Disc. Math. (1995), portant sur le calcul du facteur d'étirement entre un arbre couvrant et son graphe d'origine et sur la complexité pour obtenir un arbre couvrant de facteur d'étirement t donné. 

1er Février 2002 André Raspaud

    Local lemma de Lovasz et colorations étoilées. 

8 Février 2002 Olivier Baudon

    Recherche du plus petit ancetre commun dans un arbre, d'apres Harel et Tarjan. 

15 Février 2002 Cyril Gavoille

    Calcul du plus petit ancêtre commun avec des étiquettes 

    Résumé : Article en collaboration avec S. Alstrup, H. Kaplan et T. Rauhe.
    L'algorithme d'Harel et Tarjan, ainsi que toutes les améliorations qui ont suivi, utilisent le fait que le calcul du NCA (pour Nearest Common Ancestor) est relativement "simple" dans un arbre binaire équilibré (cf. l'exposé d'O. Baudon la semaine dernière). De manière naturelle les solutions pour un arbre quelconque utilisent un "mapping" vers un arbre binaire équilibré (d'ailleurs les variantes diffèrent dans la façon de réaliser ce mapping).
    Je montrerai une solution qui en temps linéaire associe une étiquette distincte sur O(logn) bits à chacun des sommets et qui permet de calculer en temps O(1) l'étiquette du NCA de deux sommets, connaissant seulement l'étiquette des deux sommets. Cette nouvelle solution permet un calcul "plus direct", sans mapping et sans table globale, ce qui est très utile dans un environement distribué par exemple. 

22 Février 2002 Cyril Banino et Olivier Beaumont

    Modele Maitre Esclave en environnement hétérogène 

    Résumé : Dans cet exposé, nous présenterons quelques résultats pour la distribution de tâches de calcul indépendantes sur une plateforme hétérogène (au niveau des vitesses des stations et des liens de communication). La plateforme peut être représentée par un graphe valué quelconque, dont les sommets sont les stations et les aretes les liens.
    Nous présenterons également les modèles utilisés pour représenter les delais induits par les communications dans ce type d'environnements. 

1er Mars 2002 Vacances

8 Mars 2002 David Peleg du Weizmann Institute, Israël

    Labeling Schemes for Dynamic Tree Networks 

    Résumé : Distance labeling schemes are composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute the distance between any two vertices directly from their labels (without using any additional information).

    Various applications were proposed for informative labeling schemes in general, and distance labeling schemes in particular. As those applications concern mainly large, dynamically changing networks, it is of interest to focus on distributed dynamic labeling schemes.

    The talk will consider the problem on dynamic trees. In particular, the talk will present a distributed labeling scheme for distances in the dynamic tree model, with amortized message complexity O(log^2 n) per operation, where n is the size of the tree at the time the operation takes place. The protocol maintains O(log^2 n) bit labels. This label size is known to be optimal even in the static scenario.

    Based on joint work with Amos Korman and Yoav Rodeh, to be presented at the coming STACS, Juan Les Pins. 

15 Mars 2002 Eric Sopena

    Polynômes chromatiques de graphes orientés 

22 Mars 2002 Eric Sopena

    Polynômes chromatiques de graphes orientés (suite et fin) 

29 Mars 2002 Relâche pour cause de Reunion GRAPHES et ALGORITHMES les 28 et 29 Mars

5 Avril 2002 Mohammad Hosseini

    Coloration des graphes orientés d'excès k 

12 Avril 2002 Mohammad Hosseini

    Coloration des graphes orientés d'excès k (suite et fin) 

19 Avril 2002 Cyril Banino et Olivier Beaumont

    Modele Maitre Esclave en environnement hétérogène (suite et fin) 

7 Juin 2002 Cyril Gavoille

    Complexité mémoire pour les tables de routage de déviation 2k. 

    Résumé : Le but de cet exposé est double :

       1. Montrer la relation entre le problème ouvert discuté la dernière fois (problème d'Erdös concernant le nombre maximum d'arêtes pour une maille >= 2k+2 et pour n sommets), et la taille des tables de routage garantissant des routes de déviation d < 2k, c'est-à-dire telles que la longueur des routes entre deux sommets ne dépasse pas leur distance + d.
       2. Détailler un argument issue de la << méthode d'incompressibilité >> utilisant la complexité de Kolmogorov. 

14 Juin 2002 Emeric Gioan.

    Bijections actives entre arbres couvrants et orientations des graphes (travail joint avec Michel Las Vergnas) 

    Resumé : Le polynôme de Tutte d'un graphe est une généralisation du polynôme chromatique à deux variables duales. Pour un ordre total de l'ensemble des arêtes, il en existe un modèle d'état en termes d'arbres couvrants (les 'activités' des arbres couvrants de Tutte mesurent en bref une distance aux arbres couvrants minimaux et maximaux pour l'ordre lexicographique) et un modèle d'état en termes d'orientations (les 'activités' des orientations de Las Vergnas comptent le nombre de plus petits éléments de cycles ou cocycles orientés). Il s'agit de prouver bijectivement l'égalité de ces formulations, 'bijection active' signifiant 'bijection préservant les activités'.
    Deux algorithmes duaux (l'un en termes de cycles, l'autre en termes de cocycles) définissent une bijection active entre les arbres couvrants d'activités (1,0) et les orientations acycliques ayant un unique puits adjacent à une unique source fixés.
    Via une partition de l'ensemble des orientations en 'classes d'activités', on en déduit une bijection active entre arbres couvrants et 'classes d'activités', et pour certains ordres qui existent toujours une bijection active entre arbres couvrants d'activités (i,0) et orientations acycliques ayant un unique puits fixé.
    Pour ces dernières orientations, la décomposition en 'classes d'activités' rappelle les 'composantes' de Viennot qui reposaient par contre sur un ordre total des sommets. Le fait de ne s'occuper que des arêtes permet de faire ressortir des propriétés de dualité et de prendre en compte toutes les orientations. Ce point de vue est celui des matroïdes orientés, dans lesquels les constructions précédentes se généralisent et s'interprètent géométriquement. 

21 Juin 2002 Mickael MONTASSIER

    Conception de réseaux tolérants aux pannes. 

    Resumé : Un satellite de télécommunication reçoit des signaux qui sont routés à travers un réseau d'interconnexions point à point vers des amplificateurs qui réémettent ces signaux. Cependant, pendant la durée de vie du satellite, des amplificateurs peuvent tomber en panne. A cet effet, on prévoit un nombre d'amplificateurs supérieur au nombre d'entrées de signaux. Un réseau est constitué de n entrées, n+k sorties, de liens et de commutateurs. Nous nous intéressons à deux problématiques :

       1. Quel que soit l'ensemble de k sorties en panne, les n entrées sont routées vers les n sorties valides restantes, via des chemins arêtes-disjointes.
       2. L'ensemble des n signaux est constitué de deux sous-ensembles : n-p signaux ordinaires (routés à partir d'entrées dites ordinaires) et p signaux prioritaires (routés à partir d'entrées dites prioritaires). Quels que soient l'ensemble de k pannes et l'ensemble de p sorties procurant la meilleure qualité de service, le réseau doit être en mesure de router les p entrées prioritaires vers les p sorties procurant la meilleure qualité de service et les n-p entrées ordinaires vers les n-p sorties valides restantes, le tout via des chemins arêtes-disjointes. 

    Notre objectif est de construire de tels réseaux et de minimiser le nombre de commutateurs qui les composent. 

12 Juillet 2002 Riste Skrekosvki de l'Université de Ljubiana (Slovénie)

    Two results in graph coloring. 

Année 2000/2001

6 octobre 2000 Cyril Gavoille

    Etiquetage de distances approchées

    Résumé : Présentation de quelques résultats récents sur le problème de l'étiquetage de distance sur les graphes : Il s'agit de trouver un étiquetage des sommets d'un graphe de sorte que la distance entre deux sommets puisse être calculée ou approchée par une fonction dépendant seulement de l'étiquettes des deux sommets (et pas du graphe d'où elles sont extraites).
    Etude également du cas des arbres et des graphes triangulés. 

13 octobre 2000 Relâche pour cause de voyage à Prague

20 octobre 2000 Christophe Paul

    Etiquetage de distances approchées (suite de l'exposé de Cyril)

27 octobre 2000 Denise Amar

    Denise nous présentera un contrexemple à une conjecture dans les graphes sommet-transitifs.

    D'après un article de Shim et Siran. 

3 novembre 2000 Relâche

10 novembre 2000 Yon Dourisboure

    Routage par intervalles dans le graphe Butterfly. 

17 novembre 2000 Gena Hahn (Université de Montreal)

    Quelques problemes et meme reponses sur certaines retractions des graphes, surtout Cayley. 

24 novembre 2000 André Raspaud

    Colorations étoilées 

1er décembre 2000 Relâche

8 décembre 2000 David Peleg, The Weizmann Institute

    Algorithmic Aspects of Dynamic Coalitions and Monopolies in Graphs 

    Résumé : The talk will provide an overview of recent developments concerning the process of local majority voting in graphs, its basic properties and some of its applications, from graph theoretic and algorithmic standpoints.

    (Based on joint work with Yehuda Hassin.) 

12 décembre 2000 David Peleg, The Weizmann Institute

    Near-tight time bounds for distributed MST construction 

    Résumé : The talk will present upper and lower bounds of D + sqrt{n} (ignoring logarithmic factors) on the time required for the distributed construction of a minimum-weight spanning tree (MST) in n-vertex networks of diameter D > log n, in a model allowing messages of bounded size.

    (Based on joint work with Juan Garay, Shay Kutten and Vitaly Rubinovich.) 

15 décembre 2000 Relâche pour cause de soutenance de thèse

22 décembre 2000

André Raspaud : Réponse à une question de Adrian Bondy à propos de colorations orientées

Cyril Gavoille : Introduction de la notion d'ensemble k-dominant

29 décembre 2000 Vacances

5 janvier 2001 Cyril Gavoille

    Ensembles k-dominants dans les graphes planaires 

    Résumé : Dans cet exposé je parlerai du probleme de trouver un ensemble k-dominant (ensemble de sommets S tel que d(x,S)<=k pour tout sommet x du graphe) de cardinalité minimum dans un graphe planaire de diamètre D, avec k>=D/2. Il est conjecturé que pour ce nombre est constant pour tout k>=D/2. Ici je montrerai que ce nombre est O(1/e) pour tout k>=(5/7+e)D, pour un quelconque réel e>0.

    Ce travail est la suite d'un travail en collaboration avec David Peleg, André Raspaud et Eric Sopéna. 

12 janvier 2001 Cyril Gavoille

    Ensembles k-dominants dans les graphes planaires (suite) 

    Résumé : Je continuerai la preuve que tout graphe planaire de diamètre D possède un ensemble k-dominant de taille au plus 6D si k>=5/7D. On en déduira que pour k>=(5/7+e)D il existe un ensemble k-dominant de taille O(1/e), pour tout e>0. 

19 janvier 2001 Nicolas Bonichon

    Arbres de Schnyder d'un graphe planaire maximal. Opérations, propriétés et dessins 

26 janvier 2001 Cyril Gavoille

    Ensembles k-dominants dans les graphes planaires (suite et fin) 

2 février 2001 Cyril Gavoille

    Comment router dans un arbre ? 

    Résumé : Je montrerai comment construire une structure de données distribuées permettant à un message de circuler dans un arbre à n sommets le long d'un plus court chemin. Plus précisement la structure de données occupe une place de 3logn bits par sommets et les en-têtes des messages (=adresse de la destination) ont une taille d'au plus 2.8logn bits, où la constante "2.8" est en relation avec la fonction Zéta de Riemann. Ce résultat surprenant doit être rapproché d'un résultat qui énnonce que si les en-têtes sont codées sur logn bits seulement (i.e. sont des entiers unique entre 1 et n), alors la taille de la structure de données doit être au moins de 3.7sqrt(n) bits pour certains sommets.

    Ce travail a été réalisé en collaboration avec Pierre Fraigniaud, CNRS au LRI. 

9 février 2001 Christophe Paul

    un algorithme lineaire pour la decomposition modulaire 

    Résumé : Pour calculer la decomposition modulaire d'un graphe, Capelle a montre qu'il etait suffisant de calculer une permutation factorisante des sommets. C'est une permutation des sommets telle que tout module fort appariat consecutivement. En 99, nous avions propose un algorithme de reconnaissance des cographes base sur ce principes. Nous montrerons comment on peut le generaliser sans compliquer les structures de donnees. 

16 février 2001 Christophe Paul

    Graphes de comparabilité et décomposition modulaire (suite) 

23 février 2001 Vacances

2 mars 2001 Éric Sopena

    Coloration des graphes planaires orientés 

9 mars 2001 Éric Sopena

    Coloration des graphes planaires orientés (suite) 

16 mars 2001 Olivier Baudon

    Représentation de réseaux sémantiques par des Topics Maps et fractionnement de graphe. 

    Résumé : On présentera la notion de réseau sémantique, la norme XML-Topic Map et sa représentation à l'aide d'hypergraphe et de graphes bipartis, puis les résultats de trois algorithmes de fractionnement de graphes sur ce type de graphe. 

23 mars 2001 Éric Sopena

    Classes de coloration 

30 mars 2001 Relâche

6 avril 2001 Mike Robson

    Comment trouver dans un graphe à n sommets :

        * une clique max,
        * un ensemble indépendant max,
        * ou d'autres choses, 

    en temps inférieur à 2^{n/4}. 

13 avril 2001 Akka Zemmari

    Sur la compacité des tables de routage adaptatif. 

20 avril 2001 Vacances

27 avril 2001 Pascal Weil

    Graphes, intersections de sous-groupes du groupe libre et co-rang 

4 mai 2001 Relâche pour cause de Reunion GRAPHES et ALGORITHMES les 3 et 4 mai

11 mai 2001 André Raspaud

    Colorations circulaires. 

18 mai 2001 Nasser Saheb

    Mesure d'Efficacité d'Algorithmes Probabilistes de Synchronisation 

25 mai 2001 Relâche (pont de l'Ascension)

1er juin 2001 Relâche

8 juin 2001 Relâche pour cause de soutenance de thèse de Scott Marshall

15 Juin 2001 Cyril Gavoille

    Graphes planaires, ensembles k-dominants, et largeur arborescente 

22 Juin 2001 Jaroslav Nesetril Charles (Prages)

    On a combinatorial (Coloring) theorem 

29 Juin 2001 Christophe Paul

    Décomposition en coupes et étiquetage de distance

Année 1999/2000

24 septembre 1999 Olivier Roques

    Génération uniforme de graphes planaires et de graphes non étiquetés

    Résumé : Je présenterai 2 articles : un article de Wormald, s'inspirant de Wilf et Zeilberger pour engendrer des graphes non étiquetés, i.e. les orbites des graphes étiquetés par le groupe de permutation, et un article de Alain Denise et Dominic Welsh pour engendrer de facon "presque" uniforme des graphes planaires, à partir d'une chaine de Markov.

    Vous pouvez retrouver certains des transparents présentés par Olivier Roques lors du Groupe de Travail.

1er octobre 1999 Cyril Gavoille

    Représentation implicite et étiquetage de distance des graphes

    Résumé : Une représentation implicite d'une classe de graphes à n sommets consiste à étiqueter tous les sommets de chaque graphe G par un entier pris dans l'ensemble L={1,...,2M} de sorte qu'étant données deux étiquettes on puisse décider si les sommets correspondants de G sont adjacents ou non. Si de plus on peut calculer (ou approximer) leur distance, on parle d'étiquetage de distance. On s'intéresse à minimiser M.

    Je montrerai comment évaluer M pour la classe des arbres et des graphes planaires. Notamment, je montrerai qu'il n'est pas possible de trouver M < n1/3 pour un étiquetage de distance sur la classe des graphes planaires, alors qu'un étiquetage d'adjacence (représentation implicite) peut être réalisé avec M < 4logn. 

8 octobre 1999 Guillaume Fertin

    Assignation de Fréquences et Étiquetage de Graphes

    Résumé : L'assignation de fréquences est un domaine qui a été largement étudié ces dernières années. Il s'agit d'assigner des fréquences radio à divers émetteurs, de manière à éviter les interférences. Un moyen "classique" d'étudier la chose est de se ramener à un problème d'étiquetage de graphes. Dans ces graphes, les sommets représentent les émetteurs, et les arêtes déterminent les interférences possibles entre deux émetteurs.
    Une modélisation du problème est alors la suivante : étiqueter le graphe avec des étiquettes positives entières, telles que deux sommets à distance 2 ont des étiquettes différentes, et que deux sommets voisins ont des étiquettes séparées d'au moins 2 unités. Le but étant de minimiser la différence entre la plus grande et la plus petit étiquette. Cela correspond à assigner des fréquences différentes à des émetteurs proches, et des fréquences suffisamment éloignées à deux émetteurs très proches ; le tout en utilisant une bande de fréquences la plus petite possible.

    J'évoquerai essentiellement le contenu d'un article de Griggs et Yeh (1992). Ils ont étudié le problème dans diverses familles de graphes (chemins, cycles, roues, arbres, hypercubes, graphes de diamètre 2, etc.), étudié la complexité du problème, et étudié le problème en terme du degré maximum du graphe.

15 octobre 1999 Olivier Delmas

    Conception de Réseaux de Télécom tolérants aux pannes et embarqués dans des Satellites.

    Résumé : Le problème présenté traite de la conception de réseaux de télécom embarqués dans des satellites. De tels réseaux doivent permettre de connecter des entrées, i.e. les signaux arrivant dans le satellite à des sorties, i.e. des amplificateurs, et cela même dans le cas où des amplificateurs (donc des sorties) viendraient à tomber en panne. Ces réseaux d'interconnexion sont fabriqués à partir de commutateurs et liens excessivement chers (en terme de coût) et le but recherché est de minimiser le nombre de commutateurs en respectant les contraintes suivantes :

        * chaque entrée et chaque sortie est toujours connectée à exactement un commutateur ;

        * chaque commutateur possède au plus 4 liens d'entrées/sorties (i.e. arêtes) ;

        * il y a n entrées et n+k sorties, et sur les n+k sorties, k peuvent être en panne. 

    Le but recherché est de concevoir un réseau dans lequel on peut toujours envoyer chacune des entrées sur une sortie encore valide, i.e. en état de fonctionnement.

    Nous pouvons modéliser ce problème comme suit : trouver un réseau ayant le minimum de commutateurs et dans lequel il existe toujours n chemins arêtes disjoints reliant les n entrées à un ensemble quelconque de n sorties choisies dans l'ensemble des n+k sorties possibles. Nous appelons un tel réseau : un réseau valide tolérant k-pannes.

    Dans cet exposé je donnerai plus de détails sur le problème ainsi que des résultats préliminaires. Je donnerai également une construction générale qui permet sous certaines conditions d'obtenir la construction de nouveaux réseaux tolérants aux pannes. Enfin, j'évoquerai quelques extensions à ce problème.

22 octobre 1999

    * Olivier Delmas - Conception de Réseaux de Télécom tolérants aux pannes et embarqués dans des Satellites (Suite et Fin)

    * Christophe Paul - Reconnaissance des Cographes en Temps Linéaire 

29 octobre 1999 Christophe Paul

    P4-structure of Graphs

5 novembre 1999 Relâche

12 novembre 1999 Relâche pour cause de 11 novembre

19 novembre 1999 Relâche pour cause d'Habilitation à diriger des Recherches de Myriam de Sainte Catherine (Amphi LaBRI, 14h30)

26 novembre 1999 Lali Barrière, de l'Universitat Politècnica de Catalunya (Espagne)

    Graphes de Cayley et pavages

    Résumé : Les pavages du plan ont été utilisés pour la représentation de certaines familles de graphes. Ils donnent en effet un outil pour visualiser les propriétés métriques des graphes : distance, diamètre, chemins, routage, etc.

    On peut voir en particulier que :

       1. les graphes qu'on peut representer par un pavage sont des graphes de Cayley ;
       2. tout pavage peut etre associe à un graphe. 

26 novembre 1999

    N'oubliez pas le SIF, à 15h15, amphi LaBRI.

    Cette semaine, Pierre Fraigniaud (LRI, Orsay) y parle de "Reconnaissance des graphes de Cayley abéliens colorés".

3 décembre 1999 Christophe Paul

    Graphes d'Intersection

    Résumé : Un graphe est un graphe d'intersection d'une famille d'ensembles si ses sommets sont les ensembles et deux sommets sont adjacents si les ensembles correspondants intersectent. Ces graphes sont intéressants car ils peuvent souvent être codés de manière très compacte. Les tests d'adjacence sont alors parfois en temps constant. Par ailleurs, de cette représentation peuvent découler des algorithmes très efficaces de reconnaissance ou d'optimisation.

    Nous présenterons quelques propriétés des graphes d'intersection ainsi que des exemples connus de classes de graphes d'intersection. En particulier, les classes de graphes admettant une représentation géométrique.

    Cet exposé peut être vu comme une introduction à l'exposé que nous fera Lorna Stewart au SIF le vendredi 14 janvier 2000 (15h15, Amphi LaBRI).

10 décembre 1999 Relâche

17 décembre 1999 Jaroslav Nesetril, de l'Université Charles de Prague

    On some graph theory problems by Ivan Havel and others

24 décembre 1999 Vacances

31 décembre 1999 Vacances

7 janvier 2000 Relâche

14 janvier 2000 Mike Robson

    Deterministic Radio Broadcasting

    Travail en collaboration avec Chlebus, Gasienec et Östlin.

21 janvier 2000 Relâche pour cause d'Habilitation à diriger des Recherches de Wieslaw Zielonka

28 janvier 2000 Olivier Delmas

    Diffusion en mode commutation de circuits dans le butterfly

4 février 2000 André Raspaud

    Flots antisymétriques

11 février 2000 André Raspaud

    Flots antisymétriques (Suite et Fin)

18 février 2000 Vacances d'hiver

25 février 2000 Guillaume Fertin

    Le problème de Steiner à deux paramètres : diamètre et coût

    Résumé :

    Soit un graphe G=(V,E) et D un sous-ensemble de V(G). On veut trouver le plus "petit" arbre T=(V',E') (en terme de nombre NT d'arêtes) avec E'(T) inclus dans E(G), et D inclus dans V' inclus dans V. Ce problème est appelé problème de Steiner. Ce problème est NP-complet, et la meilleure heuristique existante est à un facteur 1.5 de l'optimal.
    Appelons d(D,T) la plus grande distance (dans T) entre toute paire de sommets de D, et d(D,G) la plus grande distance (dans G) entre toute paire de sommets de D.

    Il s'agit ici de trouver une ou des heuristiques permettant de minimiser à la fois NT et le ratio d(D,T)/d(D,G). Je présenterai les résultats obtenus à ce sujet par Alexis Irlande, Jean-Claude König (LIRMM, Montpellier) et Christian Laforest (LAMI, Evry).

3 mars 2000 Guillaume Fertin

    Le problème de Steiner multi-critères (Suite)

    N'oubliez pas non plus le SIF, à 15h15, amphi LaBRI.

    Cette semaine, Sylvain Gravier (Laboratoire Leibniz, Grenoble) y parle de "Coloration par listes - une extension de la coloration".

10 mars 2000 Denise Amar

    Cycles dans les graphes de stabilité et connexité données

    Résumé : Ce problème résout une conjecture datant de 1982.

    Conjecture (Amar, Fournier, Germa, Haggkvist, Thomassen) : Un graphe k-connexe de stabilité alpha peut être recouvert par \lceil\frac{alpha}{k}\rceil cycles.

    Le résultat prouvé est le suivant:

    Théorème (Kouider) : Si H est un sous-graphe d'un graphe k-connexe G, de stabilité alpha(H) :

        * ou bien il existe un cycle de G qui recouvre les sommets de H ;
        * ou bien il existe un cycle C de G tel que la stabilité de H-C est inférieure ou égale à alpha(H)-k. 

17 mars 2000 Nicolas Bonichon

    Algorithme de dessins stratifiés de graphes planaires

24 mars 2000 Cyril Gavoille

    Etiquetage approximant la distance pour les graphes d'intervalles

    Résumé : Dans ce travail en collaboration avec Christophe Paul, je présenterai comment numéroter tout graphe d'intervalles de diamètre D avec des entiers de taille au plus log D + 1 bits, de sorte que la distance entre deux sommets quelconques puisse être approximée à 1 près à partir de leur étiquette seulement.

31 mars 2000 Relâche

7 avril 2000 Relâche

14 avril 2000 Vacances de Pâques

21 avril 2000 Olivier Delmas

    Routage optique WDM dans les arbres d'anneaux pondérés (d'après un article de Beauquier, Perennes et Tóth)

28 avril 2000 Olivier Delmas

    Routage optique WDM dans les arbres d'anneaux pondérés (Suite)

5 mai 2000 Olivier Togni (LSIIT, Strasbourg)

    Décomposition de graphes et conversion dans les réseaux optiques

    Résumé : Dans les réseaux tout-optiques, un problème classique est, pour une collection de requêtes de connexion, d'allouer à chaque requête un chemin et une longueur d'onde (couleur) de sorte que les chemins d'une même couleur soient arc-disjoints. Le nombre minimum de couleurs nécessaires W est toujours supérieur à la charge maximum portée par les arcs L et est difficile à calculer dans beaucoup de cas. On étudie dans quelle mesure le placement de convertisseurs (noeuds permettant de transformer la longueur d'onde de tout chemin qui les traverse) permet de simplifier le processus d'allocation et d'obtenir une meilleure utilisation des longueurs d'onde. En particulier, on s'intéresse au nombre minimum de convertisseurs à placer pour garantir que W soit "proche" de L. Ce problème se traduit en termes de décompositions de graphes. 

12 mai 2000 Relâche

19 mai 2000 Relâche pour cause de Commission de Spécialistes

26 mai 2000 Relâche

2 juin 2000 Relâche (Pont de l'Ascension)

9 juin 2000 Christophe Paul

    MAD-Arbre dans les Graphes d'Intervalles (d'après un article de Dahlhaus et al.)

Année 1998/1999

2 octobre 1998 Olivier Delmas

    Compromis dans les protocoles de diffusion

    Résumé : This work considers successive communication-rounds based broadcast algorithms for k-ports bidirectional-link networks under the linear model of communication cost: if algorithm A performs R_A rounds and transmits T_A bytes, its communication time is modeled as the linear function (R_A . \alpha) + (T_A . \tau), where \alpha and \tau are network parameters which abstract latency and transmission time per-byte, respectively.

    We show that to design an optimal algorithm, minimizing R_A and T_A are antinomic goals. In order to design optimal protocols we study this trade-off. The main result of this paper concerns a fully-connected N-nodes network K_N, N=(k+1)^T operating in k-ports mode. We quantify the trade-offs between the number communication rounds and the transmission time for broadcasting in T+ r rounds, for r in the range 0 <= r < T.

    It appears that a general theoretical study about such a trade-off has almost never been done. While additional broadcast rounds can be traded for exponential reductions in broadcast transmission time, this only happens for a logarithmic fraction of the range studied. For the rest of the range (i.e. preponderant part), however, additional communication rounds cannot be exploited. We are currently seeking generalizations of this work to the r >= T range in the pipelined protocols context.

9 octobre 1998 Relâche pour cause de journées TAROT au LIRMM de Montpellier Jeudi 15 octobre 1998

    N'oubliez pas la Journée Graphes du LaBRI.

16 octobre 1998 Gena Hahn, de l'Université de Montréal

    Colorations des Tournois

    Résumé : Dans ce travail, on entend par graphe un graphe orienté. Un graphe est colorié si on a donné des couleurs à ses arêtes. Il est k-colorié si au plus k couleurs sont utilisées. Un sous-graphe d'un graphe colorié est monochromatique si toutes ses arêtes ont la même couleur. Un ensemble S de sommets d'un graphe colorié est absorbant si pour tout sommet x du graphe il existe un sommet y dans S et un chemin orienté monochromatique de x vers y (un chemin de longueur 0 est monochromatique). On considère des tournois, finis ou infinis, coloriés.

    Sauer, Sands et Woodrow ont prouvé, il y a plus que 10 ans, que dans un graphe 2-colorié ne contenant aucun rayon (chemin infini orienté à partir de son origine) monochromatiqe, il existe un stable absorbant. Il en découle que tout tournoi orienté, 2-colorié sans rayon monochromatique, contient un sommet absorbant.

    Nous explorons des généralisations et des variantes de ce résultat pour des tournois finis et infinis. La présentation survole l'état des choses et des nouveaux résultats obtenus avec Pierre Ille (Marseille) et Robert Woodrow (Calgary). Quelques conjectures et quelques jolies preuves seront données, ainsi que des problèmes ouverts.

23 octobre 1998 Ondrej Sýkora, de l'Académie des Sciences de Slovaquie

    On Permutation Communications in All-Optical Rings

    Résumé : We study the wavelength problem and arc (edge) congestion problem for communicating permutation instances on a ring. We give lower bounds on the number of wavelengths in the directed case \overrightarrow{w}, in the undirected case w, and on the arc congestion \overrightarrow{\pi} and the edge congestion pi for a permutation instance I_1 on an n-vertex ring C_n. We show that all these bounds are the best possible for worst-case instances.

    From the algorithmic point of view, determining \overrightarrow{w}(C_n,I_1) and w(C_n,I_1) is NP-hard, which can be shown by a modification of the NP-hardness proof of the wavelength problem in rings, for general instances.

    This is a joint work with Mike Paterson, Heiko Schröder and Imrich Vrt'o.

30 octobre 1998 Olivier Delmas

    Compromis dans les protocoles de diffusion (Suite et Fin)

6 novembre 1998 Oleg Borodín, Siberian Branch of Russian Academy of Sciences (Novosibirsk)

    Some Extensions of Brooks' Theorem

13 novembre 1998 Imrich Vrt'o, de l'Académie des Sciences de Slovaquie

    Re-colouring Game in Graphs

    Résumé : The open problem we are addressing in this talk was proposed at SIROCCO'98 by Kranakis, with possible applications to finding a consensus in distributive networks. The problem can be viewed as a simple game on graphs, in some way similar to the game of life. The aim is to colour all the vertices of a graph, which are initially coloured with three colours 0, 1 and 2, with a single colour. The only rule is that in one move, two end-vertices of an edge can, if they are coloured differently, be re-coloured by the third colour. The question is for which graphs and initial colourings the aim can be achieved and to find an efficient algorithm if it is possible. We solve the problem completely by characterizing the graphs and initial colourings which can be transformed into a monochromatic colouring. Moreover, if the monochromatic colouring exists, then it can be found in linear number of moves.

    This is a joint work with Stefan Dobrev, Heiko Schröder and Ondrej Sýkora.

20 novembre 1998

    Session de Problèmes Ouverts n°1

    Cyril Gavoille : Ensembles dominants à distance diamètre/2 dans les graphes planaires.

    On peut trouver quelques exemples de problèmes ouverts sur cette page.

27 novembre 1998 Christophe Paul

    Calcul d'une base minimum d'une famille d'intervalles

    Résumé : Une base d'une famille F d'intervalles est un ensemble d'intervalles B tel que tout intervalle de F peut être obtenu comme l'union d'intervalles de B. Le calcul d'une base minimum est un problème équivalent aux problèmes suivants :

        * recouvrement par des rectangles de polygones horizontalement convexes ;
        * couplages sans C_4 dans un biparti convexe ;
        * nombre de sauts dans un biparti convexe ;
        * coloriage de graphes parfaits ;
        * codage de treillis particuliers ;
        * etc. 

    Nous montrerons les relations entre ces différents problèmes et présenterons les résultats connus. Quelques idées pour un algorithme glouton seront ensuite proposées.

    Il s'agit d'un travail en commun avec Lhouari Nourine (LIRMM). 

4 décembre 1998 Relâche pour cause de Journée Algorithmique de Graphes au LaBRI.

11 décembre 1998 Relâche

18 décembre 1998

    Session de Problèmes Ouverts n°2

        * Guillaume Fertin : Décomposition hamiltonienne des graphes de Knödel
        * Christophe Paul : Orientations transitives - Graphes de permutations 

8 janvier 1999 Cyril Gavoille

    Tables de routage compactes dans les réseaux aléatoires

    Résumé : Nous nous intéressons au codage ``compact des tables de routage de plus courts chemins sur un graphe G=(V,E), avec V={1,...,n}. Nous montrons que pour ``presque tous les graphes à n sommets, i.e. d'une fraction d'au moins 1-1/n^2 de tous les graphes, il existe une table de routage codable par intervalles avec au plus 3 intervalles/lien si les numéros des sommets sont quelconques (modèle ADVERSARY), au plus 2 intervalles/lien si les numéros des sommets sont permutés aléatoirement (modèle RANDOM), et enfin 1 intervalle/lien, sauf pour O(log^3(n)) liens par sommet où 2 sont requis, si les numéros des sommets peuvent être choisis à l'avance (modèle DESIGNER). Il en découle qu'en moyenne, il est possible de coder une table de plus courts chemins avec seulement n+O(log^4(n)) bits par sommets, alors que nlogn bits sont requis dans le pire cas.

    Travail en collaboration avec David Peleg du Weizmann Institute, Israël. 

15 janvier 1999 André Raspaud

    Flots et Colorations Fortes

22 janvier 1999

    Session de Problèmes Ouverts n°3

    Ondrej Sýkora

        * Bissection des graphes planaires
        * Le nombre de croisements de l'hypercube
        * Largeur de coupe cyclique de l'hypercube 

29 janvier 1999

    Discussion sur les Logiciels de Graphes

    Il s'agit ici d'une discussion ouverte sur les logiciels de graphes. La séance commencera par une intervention d'Olivier Baudon, qui présentera les interfaces sous Inca, permettant des extensions au logiciel. Une présentation de Leda (autre logiciel de graphes) sera également proposée.

5 février 1999

    Session de Problèmes Ouverts n°4

        * Eric Sopena : 16 est-il inférieur ou égal à 80 ?
        * Cyril Gavoille : sur le nombre de graphes simples non-orientés connexes 

    Si vous souhaitez parler d'un problème, veuillez en référer à Christophe Paul, qui dirigera la séance.

12 février 1999 Christophe Paul

    Un algorithme pour le double ordonnancement lexicographique des matrices 0-1

    Résumé : Toute matrice booléenne admet un ordonnancement de ses lignes et de ses colonnes tel qu'elles sont ordonnées lexicographiquement.

    Exemple :

    1 1 1 1 0
    1 1 0 0 1
    1 0 1 0 0
    0 1 0 1 1
    0 0 1 1 0

    Nous nous proposons de décrire l'algorithme proposé par Paige et Tarjan en 87.

19 février 1999 Guillaume Fertin

    Routage de 2-1 Requêtes dans l'Hypercube

    Résumé : On se place dans l'hypercube orienté symétrique de dimension n, H_n. On se donne R, une 2-1 requête dans H_n, c'est-à-dire un ensemble de couples {source,destination} appartenant à V(H_n)xV(H_n), où chaque sommet de H_n peut être utilisé au plus 2 fois comme source, et au plus 1 fois comme destination. Supposons n fixé. Pour une 2-1 requête R donnée dans H_n, on appelle ``routage un ensemble de chemins qui pour chaque couple {source,destination} va du sommet source vers le sommet destination. Si on est capable de trouver, pour chaque 2-1 requête, un routage rho_n tel que les arcs utilisés par rho_n sont deux à deux distincts, on dit que H_n est (2-1)-réarrangeable ; de plus, le routage sera dit ``arc-disjoint.

    On montre ici que pour tout n>=3, H_n n'est pas (2-1)-réarrangeable. Il est en effet possible d'exhiber une 2-1 requête g_n, construite récursivement, pour laquelle aucun routage ne peut être arc-disjoint.

    Il s'agit d'un travail réalisé en collaboration avec Olivier Baudon (LaBRI) et Ivan Havel (Académie des Sciences de la République Tchèque, Prague).

26 février 1999 Ondrej Sýkora

    Le nombre de croisements bipartis de la grille G(4,n)

    Il s'agit d'un travail réalisé en collaboration avec Olivier Baudon.

5 mars 1999 Relâche 12 mars 1999 Nicolas Hanusse

    Algorithmes de Dessin de Graphes

19 mars 1999 Relâche pour cause d'Atelier CSA (Combinatoire et Structures Aléatoires). 26 mars 1999 Olivier Delmas

    Introduction aux systèmes satellitaires

    Résumé : Au cours de cet exposé j'aborderai la notion de constellation de satellites. En effet, de tels systèmes semblent être un enjeu technologique important pour les télécommunications. Néanmoins, le terme ``constellation de satellites'' reste très vaste. Afin de mieux comprendre sa signification j'effectuerai une taxinomie des systèmes existant ou en cours de réalisation. Nous verrons notamment que les réseaux de satellites peuvent être regroupés sous différentes classes pouvant ainsi motiver des études génériques et théoriques. Je donnerai quelques idées sur des axes de recherche qui semblent être pertinents sur de tels réseaux. Nous verrons également qu'une approche complémentaire pour l'étude de ces réseaux repose sur la simulation.

2 avril 1999 Relâche pour cause de Réunion Graphes et Algorithmes au LIFO (Orléans). 9 avril 1999 Olivier Delmas

    Introduction aux systèmes satellitaires (Suite)

16 avril 1999 Nicolas Hanusse

    Routage Compact dans les Graphes de Genre Borné

    Résumé : Au plus bas niveau des communications dans les réseaux, le routage consiste à décider de la route des messages qui circulent. A chaque noeud intermédiaire, une décision est prise automatiquement par le routeur pour indiquer quel est le prochain noeud à atteindre. Le routeur choisit la route des messages le traversant en fonction d'une information contenue dans le message (le plus souvent l'adresse du destinataire) et d'une connaissance locale détenue par le routeur (table ou algorithme de routage).

    Nos travaux concernent l'étude des caractéristiques locales du routeur. Le problème du routage compact consiste à déterminer des méthodes nécessitant peu de connaissance, c'est-à-dire peu de mémoire, dans chacun des routeurs du réseau, avec un processus de décision rapide et avec les chemins les plus courts possibles.

    Nous mettons en évidence que le plongement et le dessin d'un graphe ``aide'' au routage. Nous construisons des tables de routage compact en reliant un paramètre de plongement de graphe, le genre g, à la taille des tables. Pour un réseau à n noeuds, la taille des tables est n log(g + 1)+O(n) bits avec un temps poly-logarithmique pour extraire à chaque routeur la route menant au chemin le plus court. Nos méthodes sont basées sur la représentation en k pages de graphes, codage de partitions non-croisées, ensembles dominants, codage compact de graphes, ...

    Ce travail a été réalisé en collaboration avec Cyril Gavoille.

23 avril 1999 Relâche 30 avril 1999 Nicolas Hanusse

    Routage Compact dans les Graphes de Genre Borné (Suite et Fin)

7 mai 1999 Christophe Paul

    Parcours en largeur lexicographique (1ère Partie)

14 mai 1999 Relâche 21 mai 1999 Christophe Paul

    Parcours en largeur lexicographique (2ème Partie)

28 mai 1999 Relâche pour cause de Commission de Spécialistes 4 juin 1999 Olivier Delmas

    Introduction aux systèmes satellitaires (Suite et Fin)

    Résumé : Au cours de cet exposé j'aborderai la notion de constellation de satellites. En effet, de tels systèmes semblent être un enjeu technologique important pour les télécommunications. Néanmoins, le terme ``constellation de satellites'' reste très vaste. Afin de mieux comprendre sa signification j'effectuerai une taxinomie des systèmes existant ou en cours de réalisation. Nous verrons notamment que les réseaux de satellites peuvent être regroupés sous différentes classes pouvant ainsi motiver des études génériques et théoriques. Je donnerai quelques idées sur des axes de recherche qui semblent être pertinents sur de tels réseaux. Nous verrons également qu'une approche complémentaire pour l'étude de ces réseaux repose sur la simulation.

Année 1997/1998

3 octobre 1997 André Raspaud

    Colorations

10 octobre 1997 Atelier GETGRATS 17 octobre 1997 Cyril Gavoille

    Algorithmes de diffusion et routage par intervalles

    Résumé : Récemment, David Peleg a posé la question suivante à l'école de recherche de Sienne '97 : "Est-il possible de diffuser en utilisant un nombre total de messages O(n) sur tout graphe à n sommets supportant un routage par intervalles ? (1 intervalle par arête)". Nous discuterons des éléments de réponse pour ce problème toujours ouvert.

24 octobre 1997 Olivier Baudon

    Algorithmes de coloration et de recherche d'une clique maximum

31 octobre 1997 Relâche 7 novembre 1997 Cyril Gavoille

    Compromis entre complexité mémoire et qualité du routage

    Résumé : Une fonction de routage R sur un graphe G à n sommets est une famille de fonctions R_x, x sommet de G, qui retourne pour chaque destination y le numéro de port local au sommet x sur lequel le message est à envoyer. Dans cet exposé nous nous intéresserons aux fonctions de routage de facteur d'étirement 3, ie. tel que tout chemin de routage de x à y induit par R soit au plus 3 fois plus long que la distance de x à y dans G.

    Nous décrirons une stratégie développée par Awerbuch, Bar-Noy, Linial et Peleg permettant de définir pour tout graphe à n sommets une fonction de routage de facteur d'étirement 3 nécessitant O(n^{1/2}log^2(n)) bits par sommet. Si nous avons le temps je montrerai qu'il existe des graphes où aucune fonction de routage de facteur d'étirement s<3 ne peut être définie si moins de n*log(5/4)=0.32n bits par sommets sont utilisés.

14 novembre 1997 Eric Sopena

    Un petit problème de graphes amusant

21 novembre 1997 André Raspaud

    Colorations distinguées

28 novembre 1997 Ivan Havel, de l'Académie des Sciences de la République Tchèque

    Some domination problems in a hypercube

5 décembre 1997 Cyril Gavoille

    Compromis entre complexité mémoire et qualité du routage (Suite et fin) : la borne inférieure

    Résumé : cf. Groupe de Travail du 7 novembre.

12 décembre 1997 Relâche pour cause de Journée Graphes le 11 décembre

19 décembre 1997 André Raspaud

    Graphe de Petersen et Line de l'Hypercube

9 janvier 1998 Olivier Baudon

    Partage de graphes

    Résumé : On s'intéresse au problème suivant : soit G un graphe connexe à n sommets, modélisant un ensemble de ressources organisées en réseau (processeurs, stations). Peut-on assurer que V(G) est partageable en k morceaux V1, ..., Vk de tailles n1, ..., nk, tels que tout sous-graphe induit par un ensemble de sommets Vi soit connexe ?

16 janvier 1998 Olivier Baudon

    Partage de graphes (Suite et fin)

23 janvier 1998 Guillaume Fertin

    Echange total en temps linéaire

    Résumé : On s'intéresse au problème suivant : dans un graphe, chaque sommet possède une information et doit la transmettre à tous les autres. On suppose que le modèle est full-duplex et qu'un sommet peut communiquer avec un seul de ses voisins à la fois (modèle 1-port). Le temps de communication entre deux sommets, quant à lui, dépend de la longueur du message communiqué. On s'intéresse alors au temps minimum nécessaire pour communiquer dans le graphe complet Kn, de manière synchrone ou asynchrone. Nous verrons que si la réponse est connue dans le cas où n est pair, tout se complique dans le cas impair...

30 janvier 1998 Eric Sopena

    Jeu de go dans les graphes

6 février 1998 Anne Bottreau

    Arbres recouvrants et les revêtements

13 février 1998 Cyril Gavoille

    Techniques probabilistes appliquées au routage

    Résumé : Récemment, nous avons proposé une méthode permettant de construire pour tout graphe un routage de "compacité" au plus O(sqrt(nlogn)) (nombre maximum d'intervalles d'adresses consécutives utilisant le même lien à partir d'un sommet) et de "facteur d'étirement moyen" borné par 3 (moyenne sur toutes les paires (u,v) du rapport entre longueur du chemin de routage et distance entre u et v).

    Je détaillerai une preuve montrant que pour certains graphes notre méthode (basée sur la sélection randomisée de certains sommets) conduit à un facteur d'étirement moyen > 3-o(1) avec probabilité 1-o(1). Si j'ai le temps, je détaillerai également la preuve montrant que pour "presque tous" les graphes à n sommets, notre méthode produit un facteur d'étirement s tel que : 1.875-o(1) < s < 1.875+o(1).

20 février 1998 Relâche 27 février 1998 Olivier Togni

    Indice Optique des Graphes Circulants

6 mars 1998 Olivier Togni

    Indice Optique des Graphes Circulants (Suite et fin)

André Raspaud

    Line de l'hypercube

13 mars 1998 Laurence Vignal

    Coloration orientée incrémentale

    Résumé : Une coloration orientée incrémentale est une coloration orientée obtenue par un algorithme qui colorie, en respectant une certaine heuristique, les sommets d'un graphe pris dans un ordre prédéfini, sans jamais recolorier un sommet. On étudie en particulier l'algorithme First-Fit. On cherche à savoir si pour tout graphe orienté, il existe un ordre sur les sommets tel que le nombre de couleurs utilisées par First-Fit pour colorier ce graphe muni de cet ordre est exactement le nombre chromatique orienté du graphe.

20 mars 1998 Jérôme-Olivier Durand-Lose

    "Sense of direction", d'après Flocchini, Mans et Santoro

    Résumé : Dans un graphe où chaque noeud possède des étiquettes pour identifier chacune des arêtes sortantes, le sens de la direction permet de dire si deux chemins issus d'un même sommet aboutissent au même sommet, en ne connaissant que la suite des étiquettes utilisées et sans savoir d'où sont issus ces chemins.

    Dans un premier temps, je définirai formellement le concept, ensuite j'essaierai d'en fournir une approche intuitive grace à une série d'exemples et de contre-exemples.

    Je montrerai ensuite que l'on peut munir simplement le produit de 2 graphes ayant un sens de la direction d'un sens de la direction.

    Je montrerai finalement que le sens de la direction permet de connaître localement tout le graphe - avec la puissance de calcul que cela fournit.

27 mars 1998 Laurence Vignal

    Coloration orientée incrémentale (Suite et fin)

3 avril 1998 Relâche 10 avril 1998 Jarik Nesetril

    On Some Coloring Problems

17 avril 1998 Relâche 24 avril 1998 Jérôme-Olivier Durand-Lose

    "Sense of direction", d'après Flocchini, Mans et Santoro (Suite)

    Résumé : Dans la suite de la présentation du << Sense of direction >> de Flocchini et al., nous ferons un exposé en 3 parties :

        * Rappel rapide des définitions :
              o SoD
              o Cayley graphs 
        * Démonstration de : << si un graphe d-régulier possède un SD faible (symétrique) avec d étiquettes, alors c'est un graphe de Cayley avec un étiquetage canonique >>
        * (optionnel)
              o Rappel de ce qu'est un revètement
              o Condition de passage d'un SD à un revétement 

1er mai 1998 Férié 8 mai 1998 Férié 15 mai 1998 Petra Spickova, de l'Université Charles de Prague

    Homomorphism Duality of Oriented Graphs

22 mai 1998 Danny Krizanc, Carleton University

    Distributed Online Frequency Assignment in Cellular Networks

    Résumé : A cellular network is generally modelled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multicoloring problem on a weighted version of such a graph where the weight associated with a vertex represents the number of calls to be served at the vertex, which is assumed to change over time. In this talk, we describe a framework for studying distributed online frequency assignment in cellular networks. We present the first distributed online algorithms for this problem with proven bounds on their competitive ratios. We show a series of algorithms that use information about increasingly larger neighborhoods of the vertices, thereby achieving better competitive ratios. In contrast, we show lower bounds on the competitive ratio of some natural classes of online algorithms. Some of our algorithms are optimal for the classes of algorithms studied.

    This is joint work with J. Janssen, L. Narayanan and S. Shende. 

29 mai 1998 Flaminia Luccio, de l'Université de Milan

    Compact Routing in Series-Parallel Graphs

    Résumé : We present some work in progress about routing with compact tables in networks whose underlying topology is a Series-Parallel Graph, a well-known planar sub-class of graphs. In particular we show a technique to route with few intervals and a stretch factor at most 3.

    This is a joint work with Cyril Gavoille. 

5 juin 1998 Relâche pour cause de Soutenance de Thèse de Philippe Duchon.

12 juin 1998 Relâche pour cause de Commission de Spécialistes.

19 juin 1998 Relâche pour cause d'ALTEC'98 (Prague)et de WG'98 (Smolenice).

26 juin 1998 Jérôme-Olivier Durand-Lose.

    Exclusion Mutuelle Auto-Stabilisante

Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar