2005-2006

30 Juin 2006 - Coloration acyclique impropre (par listes) - Louis Esperet

On considère une coloration impropre des graphes, dans laquelle chaque classe de couleur a un degré max borné. On étudie la coloration acyclique impropre par listes de certaine classes de graphes et on montre par exemple que les graphes planaires extérieurs sont acycliquement (2,5)-choosable (i.e. 2-choosable avec des classes de couleur de degré max au plus 5) et que les graphes de degré max. 3 sont acycliquement (3,1)-choosable. On donne aussi un lien entre cette coloration et la conjecture de Borodin et al "les graphes planaires sont acycliquement 5-choosable".

23 Juin 2006 - Gathering in specific radio networks - Nelson Morales (INRIA Sophia Antipolis)

We address the problem of gathering information into a central node of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area larger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most $\dt$ in the graph, but when doing so it generates interference that does not allow nodes at distance up to $\di$ ($\di \ge \dt$) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. Because this problem is hard to approximate in general graphs, we study \emph{good} approximations in some specific topologies, like the path, balanced stars and the 2 dimensional grid. In all these cases we provide algorithms whose performance differs only by an additive constant from the theoretical minimum.

16 Juin 2006 - About the Minimum Energy Broadcasting in Wireless Ad Hoc Networks - Alfredo Navarra (Université de L'Aquila, Italie)

The talk presents latest results mainly on the performance of the Minimum Spanning Tree (MST) heuristic for the Minimum Energy Broadcast Routing (MEBR) problem. The MEBR basically consists in throwing n wireless devices on a d-dimensional Euclidean space while setting one of them as the root. A node x transmitting with power energy P_x can reach a node y at distance |x,y| whenever P_x >= Beta |x,y|^alpha for suitable constants Beta and alpha. The goal is to perform the broadcast pattern of communication from the root while minimizing the total consumed energy. One of the most famous heuristic studied in the literature is definitely the MST one. It creates a minimum spanning tree from the fixed root over the complete directed weighted graph G obtained as follows.The wireless devices represent the nodes of G. Every two nodes x, y are connected by a directed edge with weight equal to Beta |x,y|^alpha. Visiting the obtained tree from the root, each node is assigned a power of transmission equal to the heavier outgoing edge. The problem will be discussed from both experimental and theoretical point of views.

2 Juin 2006 - Théorèmes de décomposition pour les graphes excluant un mineur. - Cyril Gavoille

Robertson et Seymour ont récemment donné (dans "Graph Minors 16, 2003") une caractérisation des graphes ne contenant pas un graphe arbitraire H comme mineur. Cette caractérisation est basée sur une décomposition arborescente très complexe des graphes. Basé sur cette dernière, nous montrons que les graphes excluant un mineur sont "k-chemins séparables" où k est une constante ne dépendant que du mineur exclu. Grosso modo cela signifie que de tels graphes peuvent être coupé en deux en supprimant au plus k plus courts chemins. La propriété de k-chemin séparable a de nombreuses applications: routage, oracle de distance, petits-monde, etc.

Dans cette exposé je me contenterai de donner les concepts de base pour comprendre l'énoncé du théorème de décomposition de Robertson et Seymour, ainsi que les idées principales permettant de montrer que les graphes excluant un mineur sont k-chemins séparables.

Mots-clés: décomposition arborescente, surface orientable, surface non-orientable, vortex, joint, torso, etc.

19 Mai 2006 - Graphes décomposables. - Olivier Baudon

Il s'agit de caractériser les graphes d'ordre n tels que pour toute décomposition de n en une somme de k entiers a1, ..., ak (a1 + a2 + ... ak = n), il existe une partition des sommets de G en k sous-ensembles A1, ... Ak tels que pour tout i |Ai| = ai et le sous-graphe induit par Ai est connexe. L'exposé présentera les résultats récents de Barth et Fournier sur les arbres et quelques questions ouvertes.

28 avril 2006 - Mobile Agent Rendezvous in a Synchronous Torus. - Euripides Markou

We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a striking {\em computational difference} between one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they have $o(\log n)$ memory, while they can perform rendezvous with detection as long as they have one unmovable token and $O(\log n)$ memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitrary $n \times m$ (respectively, $n \times n$) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in a $n \times m$ torus.

14 avril 2006 - Conception de réseaux embarqués tolérants aux pannes. - Mickaël Montassier

La fiabilité des réseaux embarqués dans les satellites de télécommunication, maillons essentiels dans la chaîne de la diffusion d'information, est un enjeu important. Comment concevoir des réseaux embarqués à faible coût capables de tolérer un certain nombre de pannes et de continuer à propager l'information ? Nous donnons des éléments de réponse à cette problématique posée par Alcatel Space Industries en présentant des réseaux de coût minimum supportant un nombre de pannes donné.

7 avril 2006 - A revival of the girth conjecture. - Tomas Kaiser

It was conjectured by Jaeger and Swart that non-3-edge-colourable cubic bridgeless graphs have bounded girth. Although this `Girth Conjecture' has been disproved, we show that its analogue for the circular edge-colouring `holds' in an asymptotic sense. This is joint work with Dan Kral, Riste Skrekovski and Xuding Zhu.

31 Mars 2006 - Classes de graphes définies par intersection et/ou par chevauchement. - Pascal Ochem

On parlera de deux hiérarchies de classes de graphes, définies respectivement par des intersections et des chevauchements d'objets connexes. Certaines classes apparaissent dans les deux hiérarchies. Par exemple, un graphe "circle" est le graphe d'intersection de cordes d'un cercle, et c'est aussi graphe de chevauchement de sous-chemin d'un chemin. Il y aura des résultats d'inclusions de classes de graphes, dont certains découlent du résultat suivant : la classe "interval filament" (définie par intersection) correspond à la classe des chevauchements de sous-graphes d'un caterpillar. C'est travail en commun avec Jérémie Chalopin et Daniel Gonçalves.

24 Mars 2006 - Extraction de sous-graphes tres denses dans un graphe de tres grande taille. - Yon Dourisboure.

Etant donne un graphe, en extraire des sous-graphes tres denses, tels que les cliques ou les bibartis complets, est un probleme connu pour sa grande complexite algorithmique. C'est pourtant un probleme qui intervient notamment dans la recherche de communautes dans le graphe du web. Ce graphe, dont les sommets representent les pages web et les arcs representent les hyperliens entre les pages, possede a ce jour quelques milliards de sommets et dizaines de milliards d'arcs. Les algorithmes classiques sont donc inutilisables.

Nous presenterons une heuristique permettant d'extraire de grands sous-graphes tres denses dans des graphes de tres grande taille. Pour l'instant, cette heuristique a ete testee sur des graphes ayant jusqu'a 40 Millions de sommets et 1 Milliards d'arcs, les resultats ont ete obenus en quelques minutes avec une machine a 1.4GHz ayant 1.5Go de memoire.

17 Mars 2006 - étiquetage compact par "parcours bondissant". - Arnaud Labourel.

Un étiquetage d'adjacence d'un famille F de graphes consiste en une fonction qui associe à chaque sommet des graphes de F une étiquette binaire, tel que l'on puisse calculer l'adjacence entre 2 sommets à partir de leurs étiquettes. Nous donnons une fonction d'étiquetage pour la famille des caterpillars et des arbres binaires d'au plus n sommets avec des étiquettes de taille au plus log n+O(1) bits grâce à une nouvelle méthode d'étiquetage nommée "parcours bondissant".

3 Mars 2006 - Colorations injectives. - André Raspaud.

Une coloration injective d'un graphe G=(V,E) est une coloration des sommets telle que deux sommets reliés par une chaîne de longueur 2 ont des couleurs différentes. Nous donnons de nouvelles bornes pour le nombre chromatique injectif d'un graphe.

24 Février 2006 - Décomposition distribuée de graphe. - Bilel Derbel.

On s'interesse à un algorithme de décompostion de graphe permettant d'obtenir des clusteurs (ensembles de noeuds) avec un petit rayon et faiblement connectés entre eux. Plusieurs applications distribuées utilisent ce type de décompostion comme point de départ, d'ou l'importance de construire ce type de décompositoin de facon efficace. Je présenterais un algorithme de décomposition complètement distribué ayant une complexité linéaire en temps. Ensuite, je présenterais un algorithme produisant la même décompositon en temps sous-linéaire. Enfin, je présente une application aux spanners (graphes couvrants peu denses).

10 Février 2006 - Inégalites de familles de cliques (suite et fin). - Arnaud Pêcher.

Les inégalités de familles de cliques forment une famille d'inégalités qui sont valides pour le polytope des stables d'un graphe (quelconque). Lors du précédent groupe de travail, nous avons vu comment majorer leur rang de Chvatal, mais je n'ai pas précisé l'intérêt de ces inégalités.

Ce sera chose faite dans cette seconde partie!

20 Janvier 2006 - A propos du rang de Chvatal des inégalites de familles de cliques. - Arnaud Pêcher.

Les inégalités de familles de cliques forment une famille d'inégalités qui sont valides pour le polytope des stables d'un graphe (quelconque). Gianpaolo Oriolo a écrit qu'elles ne résultaient pas de techniques d'arrondi classiques, et de fait, la preuve publiée de leur validité est assez ingénieuse. Dans cet exposé, je vais expliquer comment obtenir une majoration du rang de Chvatal de ces inégalités. Cette majoration donne une preuve différente de leur validité, basée uniquement sur des techniques élémentaires d'arrondi...

13 Janvier 2006 - Méthode des ellipsoides et applications. - Olivier Beaumont.

Dans un premier temps, je presenterai la méthode des ellipsoides pour la programmation linéaire (en nombres rationnels). Nous verrons ensuite que cette méthode peut permettre de construire aisément des algorithmes polynomiaux pour de nombreux problèmes (en particulier, on regardera des problèmes de coloriage, dans leur version fractionnaire, pour changer :-) ).

16 Décembre 2005 - Arc-coloration orientée (suite et fin). - Alexandre Pinlou.

9 Décembre 2005 - Arc-coloration orientée. - Alexandre Pinlou.

Une arc-coloration orientée d'un graphe orienté G est une application qui assigne à chaque arc de G une couleur telle que (i) deux arcs consécutifs prendrons des couleurs différentes et (ii) si deux arcs consécutifs sont coloriés respectivement a et b, alors G ne contiendra pas deux arcs consécutifs coloriés respectivement b et a. L'index chromatique orienté d'un graphe orienté est le plus petit k tel que G admet une k-arc-coloration orientée. Nous montrerons que nous sommes capables d'obtenir des bornes sur l'index chromatique orienté en fonction de paramètres déjà connus : nombre chromatique, nombre chromatique orienté, nombre chromatique acyclique. Nous montrerons également des résultats obtenus sur certaines classes de graphes telles que les graphes planaires ou les graphes cubiques.

25 Novembre 2005 - L'orientation transitive peut-elle aider à résoudre les problèmes sandwich? - Emmanuelle Lebhar.

Les problèmes de graphes sandwich se situent entre les problèmes de complétion et de reconnaissance de graphes. Précisément, un problème de graphe sandwich est la donnée d'un graphe G=(V,E), d'un sous-graphe (V,F) de G (non nécessairement induit) et d'une propriété de graphe Pi. On cherche à savoir s'il existe un sous graphe H=(G,E_s) de G qui vérifie Pi et tel que E_s contienne E. Lors de leur présentation de ce problème, Golumbic et al ont donné plusieurs résultats algorithmiques et de complexité pour des sous-familles des graphes parfaits. Nous nous intéressons aux graphes de comparabilité qui admettent une orientation transitive, et nous étudions dans quelle mesure l'ajout d'une orientation peut simplifier, ou rendre plus complexe, un problème sandwich non orienté. Nous montrons que pour certaines classes de graphes, il est possible d'obtenir un algorithme polynomial pour le problème de l'ordre sandwich, tandis que le problème de graphe sandwich associé est NP-complet; et vice-versa pour d'autres classes. Nous étudions en particulier les cographes, les graphes d'intervalles, les graphes de permutation et la semi-clique.

18 Novembre 2005 - Optimisation de trajets de collecte. - Eric Sopena.

Nous présentons une problématique issue d'une collaboration avec une entreprise conceptrice d'un logiciel de suivi et d'optimisation de trajets de collecte (par exemple collecte d'ordures ménagères).

Le problème considéré se modélise naturellement comme un problème d'optimisation combinatoire sur un graphe nécessitant la définition d'heuristiques adaptées. Ce problème est connu dans la littérature sous le nom de "Rural Chinese Postman Problem on Mixed Graphs", possède de nombreuses variantes, et constitue un domaine actif de recherche.

Nous présenterons dans un premier temps le problème en question et ses contraintes, puis nous décrirons les solutions apportées jusqu'ici et terminerons par les problèmes en cours d'étude.

28 Octobre 2005 - Matroids and Complexity. - Dillon Mayhew.

A matroid is a finite set, along with a structured family of subsets. Important examples arise from graphs, and from matrices with entries in a field. For 25 years or more, the study of matroid algorithms and their computational complexity has essentially been restricted to small families of matroids, such as those that arise from a graph or a matrix over a field. The reason the research has been restricted in this way is that in other cases the size of the input would be very large. It was thought that all problems would therefore be trivially solvable in polynomial time. However, there are some fairly simple examples which show that some matroid problems are likely to be intractable, even using this scheme of 'large' inputs. Deciding which problems are tractable, and which probably are not under this scheme is a potentially rich area of research in matroid complexity.

The talk will include an introduction to matroids, with examples, an overview of some results from matroid complexity, and an indication of potential directions for future research.

21 Octobre 2005 - Succinct routing tables for planar graphs. - Cyril Gavoille.

Je parlerai en fait d'une nouvelle décomposition en "clusters" des graphes excluant un mineur fixé, par exemple K_{r,r} avec r=3. En ligne de mire toujours le routage compacte, mais cette décomposition donne surtout une preuve plus simple de la décomposition "KPR" (Klein-Plotin-Rao '93). Travail en commun avec Ittai Abraham et Dahlia Malkhi de l'Université de Jérusalem.

14 Octobre 2005 - Coloration VS. coloration par listes. - Mickaël Montassier.

7 Octobre 2005 - Coloration linéaire par listes. - Louis Esperet.

Une coloration linéaire d'un graphe G est une coloration propre des sommets de G tels que le sous graphe induit par l'union de deux classes de couleur quelconques est une forêt de chaines. On a étudié le nombre chromatique linéaire (le plus petit nombre de couleurs dans une coloration linéaire) et le nombre chromatique par listes pour différentes familles de graphes (petit degré maximum, planaires-extérieurs, de mad borné, planaire,...). On donnera des bornes pour le nombre chromatique linéaire par listes dans le cas de chacune de ces familles, ainsi qu'un résultat de NP-complétude pour le problème de la coloration linéaire.