Archives
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