2008-2009
2008-2009
29 mai 2009 - Spanners Géométriques : liens étroits entre triangulations de TD-Delaunay et demi-Thêta-graphes - Nicolas Bonichon.
Résumé : Un s-spanner est un sous-graphe H d’un graphe G, tel que pour tout couple de sommets, la distance dans H soit au plus s fois la distance dans G. Les Thêta-graphes sont une famille classique de spanner du graphe Euclidien (graphe complet sur n sommets du plan dont la longueur d'une arête est égale à la distance Euclidienne entre ses extrémités). Nous montrons qu’un demi-Thêta-graphe avec thêta = pi/3 est un 2-spanner du graphe Euclidien.
Pour obtenir ce résultat nous étudions les liens étroits qu’il y a entre les 1/2-théta-graphes, les surfaces orthogonales coplanaires et les triangulations de TD-Delaunay.
Nous présenterons également plusieurs résultats secondaires et généralisations possibles liés à ces correspondances.
(Travail réalisé en collaboration avec Cyril Gavoille, Nicolas Hanusse et David Ilcinkas).
15 mai 2009 - On the Path Separability of Planar Graphs - Émilie Diot.
Résumé: It is known that every weighted planar graph with $n$ vertices contains three shortest paths whose removal halves the graph into connected components of at most $n/2$ vertices. Whether this property remains true with the use of two shortest paths only is an open problem.
We show that two shortest paths are enough for a large family of planar graphs, called face-separable, composed of graphs for which every induced subgraph can be halved by removing the border of a face in some suitable embedding of the subgraph. We also show that this non-trivial family of graphs includes unbounded treewidth graphs.
24 avril 2009 - De l'incidence des matroides sur les arrangements, polytopes et noeuds, et pavages avec Frobenius - Jorge Ramirez Alfonsin (Paris 6).
Résumé : Dans cet exposé, je présenterai plusieurs résultats obtenus en utilisant la théorie des matroïdes orientés, liés aux problèmes géométriques (concernant les polytopes et les arrangements d'hyperplans) et topologiques (relatifs aux noeuds). J'aborderai également le problème diophantien de Frobenius, notamment dans le cadre d'une application récente à un problème de pavage.
10 avril 2009 - Game coloring on the toroidal grid - JiaoJiao Wu.
Résumé : A toroidal grid graph is the Cartesian product of two cycles. We prove that the maximum game chromatic number and maximum game coloring number of toroidal grids are equal to five.
3 avril 2009 - Star coloring - Min Chen.
Résumé : A proper coloring of the vertices of a graph G is called a star-coloring if the union of every two color classes induces a star forest. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring phi such that phi(v) is in L(v). If G is L-star-colorable for any list assignment L with |L(v)| at leat k for any vertes v, then G is called k-star-choosable. The star list chromatic number of a grah G is the smallest integer k such that G is k-star-choosable. In this talk we present new bounds for the star list chromatic number of subcubic planar graphs.
20 mars 2009 - Graphes récursivement arbitrairement décomposables - Olivier Baudon.
Résumé : Après un rappel des définitions et résultats sur les graphes arbitrairement sommet-décomposables, on présentera trois sous-classes de ces graphes : la version on-line, et les versions récursives et fortement récursives. On montrera que les graphes "fortement récursivement arbitrairement sommet-décomposables" (SR-AVD) sont exactement la classe des graphes claw-and-net free. Pour les "récursivement arbitrairement sommet-décomposables" (R-AVD), en s'appuyant sur des résultats précédents sur la version on-line, on donnera la liste exhaustive des arbres et soleils R-AVD, ainsi que quelques résultats sur un classe de graphes 2-connexes : les ballons.
13 mars 2009 - Graph Searching Games and Routing Reconfiguration in WDM Networks - Nicolas Nisse (Projet MASCOTTE - INRIA Sophia Antipolis).
Résumé : In graph searching games, a team of searchers is aiming at capturing an invisible fugitive running in a graph, or, equivalently, at clearing a contaminated network. These problems are motivated by several aspects of theoretical computer science, including computational complexity, minor graph theory and distributed algorithms. In this talk, we present a short literature survey and then, we focus on a more practical application, the routing reconfiguration problem in WDM networks. In this context, the goal consists in switching a set of connection requests from current routing to another pre-determined routing in order to optimize the resources of the network. We show how the problem can be modelled in terms of graph searching and present some results we obtained using this framework.
20 février 2009 - Le nombre d'arbres recouvrants de graphes de degré borné - Mike Robson.
Résumé : Nous cherchons des bornes inférieures sur le nombre SP(G) d'arbres recouvrants d'un graphe connexe G de degré borné par d en termes de son nombre cyclomatique \mu (nombre d'arêtes - nombre de sommets + 1). Nous définissons \beta_d, inf{x|SP(G) \ge x^\mu(G) pour tout G connexe de degré borné par d} et nous conjecturons que \beta_d est toujours donné par G=K_{d+1}. Cette conjecture est prouvée pour d=2, 3, 4 et 5 ; nous donnons des bornes inf sur \beta_d pour d de 6 à 11.
13 février 2009 - Le nombre chromatique ludique des arbres et des chenilles - Adrien Guignard.
Résumé : Le nombre chromatique ludique est issu d'un jeu de coloration [G,k] à deux joueurs où Alice tente de colorier tout graphe G avec k couleurs et Bob essaye de l'en empêcher. Ce nombre est le plus petit k pour lequel Alice a une stratégie gagnante, en jouant la première. Si Bob joue le premier coup, on parlera de nombre chromatique ludique misère. Comme tout arbre a un nombre chromatique ludique d'au plus 4 (et d'au moins 3 s'il est de diamètre supérieur à 4), il est intéressant de caractériser les arbres de nombre chromatique ludique 3. Nous montrerons comment caractériser les 1-chenilles de nombre chromatique ludique 3. Dans le cas des arbres généraux, nous présenterons quelques réductions qui permettent de limiter l'étude du problème à une famille plus restreinte d'arbres.
30 janvier 2009 - Consecutive ones matrices for orthogonal packing problems - Arnaud Pêcher.
Résumé : La modélisation par des graphes par Feketete et Shepers (1997) du problème du placement de formes orthogonales dans un conteneur a permis de faire un saut quantitatif quant à la taille des problèmes traités. En effet, en représentant les solutions par des graphes d'intervalles, de nombreuses symmétries (i.e. des solutions identiques) sont éliminées. Fulkerson et Gross ont démontré qu'un graphe est un graphe d'intervalle si et seulement s'il a au plus n cliques maximales (n étant son nombre de sommets), et celles-ci peuvent être ordonnées, de telle sorte que pour tout sommet, les cliques le contenant soient consécutives. Avec Cédric Joncour, nous* avons mis au point un nouvel algorithme basé sur cette caractérisation des graphes d'intervalles. Mon exposé présentera les grandes lignes de cet algorithme et les résultats obtenus sur les jeux de tests classiques. Il n'y aura donc pas de polytopes (sic) et pas beaucoup de maths non-plus (re-sic). nous* = surtout Cédric"
23 janvier 2009 - Adding a distance constraint to Bin Packing and Bin Covering Problems - Hubert Larchevêque.
Résumé : Nous nous intéressons à deux problèmes NP-Complet classiques, le Bin Covering et le Bin Packing, admettant respectivement un PTAAS et un PTAS. Nous étudions une version contrainte de ces problèmes, lorsque les éléments à grouper se trouvent à une certaine distance les uns des autres. Le but est d'alors de former des groupes d'éléments ayant au moins un certain poids (resp. au plus un certain poids) de façon à ce que deux éléments présents dans le même groupe ne soient pas à une distance supérieure à une certaine borne fixée dans l'instance du problème. Pour ces deux problèmes de Bin Covering et de Bin Packing avec Distance Contrainte, nous démontrons l'impossibilité d'approximer à n'importe quelle constante chacun des deux problèmes en les réduisant pour l'un au problème du Maximum k-Dimensional Matching, et, pour l'autre, au problème de Minimum Clique Partition. Ces résultats d'inapproximabilité sont étendus au cas où la contrainte de distance est relâchée en utilisant une augmentation de ressource: une solution est autorisée à construire des groupes de diamètre (2-e).dmax, e>0, tandis qu'elle sera toujours comparé à l'optimal contraint à dmax. Nous présentons ensuite pour chacun de ces deux problèmes un algorithme d'approximation utilisant respectivement une augmentation de ressource sur le diamètre de 3 et de 2, permettant une approximation de la solution optimale à respectivement un facteur 1/3 et 3.
19 décembre 2008 - Compter les couplages parfaits dans les graphes cubiques - Louis Esperet.
Résumé : Lovasz et Plummer ont conjecturé dans les années 70 que les graphes cubiques 2-arete-connexes ont un nombre exponentiel de couplages parfaits. Cela a été montré pour les graphes bipartis en 1979 par Voorhoeve, et tres récemment pour les graphes planaires par Chudnovsky et Seymour. Dans le cas général les meilleures bornes connues sont linéaires : Edmonds, Lovász, et Pulleyblank, et indépendamment Naddef, ont prouvé en 1982 que la dimension du polytope des couplages parfaits d'un graphe cubique 2-arete-connexe a n sommets est au moins n/4+1 (ce qui implique directement qu'ils ont au moins n/4+2 couplages parfaits). En utilisant un résultat récent de Král', Sereni, et Stiebitz, nous montrons que tout graphe cubique 2-arete-connexe a n sommets a au moins 3n/4-10 couplages parfaits. Notre preuve est inductive et repose largement sur la "brick and brace decomposition" introduite par Edmonds, Lovász, et Pulleyblank en 1982.
(travail en commun avec Daniel Král', Petr Škoda, et Riste Škrekovski)
12 décembre 2008 - Structure des graphes sans mineur K_2,4 - Cyril Gavoille et Youssou Dieng.
Résumé : Nous nous intéressons à la structure des graphes ne contenant pas comme mineur un graphe H. De nombreuses caractérisations sont connues lorsque H contient au plus 5 sommets, en particulier pour H=K_5 [Wagner - 1937]. Le problème est beaucoup plus difficile lorsque H contient 6 sommets, voir plus. Par exemple, la caractérisation des graphes sans mineur K_6 est toujours non résolue, et est en relation avec la conjecture d'Hadwiger concernant le nombre chromatique des graphes sans K_r (voir [K. Kawarabayashi - SODA'07] pour une plus ample discussion sur l'importance des graphes sans mineur K_6). Citons également la conjecture de Jörgensen - 1994: Conjecture: Tout graphe 6-connexe G sans mineur K_6 possède un sommet u tel que G{u} est planaire. Nous prouvons le résultat suivant: Théorème: Tout graphe 2-connexe G sans mineur K_{2,4} possède deux sommets u,v tels que G{u,v} est planaire-extérieur. En particulier, les graphes sans mineur K_{2,4} sont de largeur arborescente au plus 4, améliorant un résultat de [Bodlaender et al. - 1997]. Cette borne est optimale à cause de K_5. En fait, nous construisons un algorithme de complexité linéaire qui pour tout graphe 2-connexe soit exhibe un mineur K_{2,4} ou bien détermine deux sommets dont la suppression rend le graphe planaire-extérieur. Le théorème précédent ne peut pas être étendu trivialement pour les graphes sans mineurs K_{2,r} avec r > 4. En effet, nous montrons que pour tout entier k, il existe un graphe 2-connexe sans mineur K_{2,5} pour lequel il est nécessaire d'enlever k sommets pour le rendre planaire-extérieur.
5 décembre 2008 - Mots, graphes et morphismes sans répétition : quelques résultats et questions - Gwénaël Richomme (LARIA, Amiens).
Résumé : La résolution de nombreux problèmes nécessite une bonne compréhension de phénomènes de répétitions dans les mots. Une première partie de l'exposé présentera quelques résultats récents sur un problème ouvert dans les années 1980 : est-il possible de décider si un morphisme préserve les mots sans puissance k ? Une deuxième partie de l'exposé s'interrogera sur la généralisabilité d'une telle approche aux graphes sans répétition introduits récemment par Alon, Grytczuk et al.
14 novembre 2008 - Résumé de cubes de données - Radu Tofan et Nicolas Hanusse.
Résumé : Un cube de donnée est une structure de donnée utilisée en fouille de données. Elle peut être modélisée par un hypercube orienté, étiqueté et pondéré. L'objectif de ce travail est de construire un ensemble de sommets S de petite taille tel que tout sommet possède un ancêtre dans S de poids comparable.
10 octobre 2008 - Periodic exploration using an agent with small memory - David Ilcinkas.
Résumé : We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an arbitrary undirected graph G in a periodic manner. Graphs are supposed to be anonymous, that is, nodes are unlabeled. However, while visiting a node, the robot has to distinguish between edges incident to it. For each node v the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in minimisation of the length of the exploration period.
This problem is unsolvable if the local port numbers are set arbitrarily, see [Budach 1978]. However, surprisingly small periods can be achieved when assigning carefully the local port numbers. Dobrev et al. [SIROCCO 2005] described an algorithm for assigning port numbers, and an oblivious agent (i.e. agent with no memory) using it, such that the agent explores all graphs of size n within period 10n. Providing the agent with a constant number of memory bits, the optimal length of the period was proved in [Gasieniec et al. JCSS 2008] to be no more than $3.75n$ (using a different assignment of the port numbers). In this paper, we improve both these bounds. More precisely, we show a period of length at most (4+1/3)n for oblivious agents, and a period of length at most 3.5n for agents with constant memory. Moreover, we give the first non-trivial lower bound, 2.8n, on the period length for the oblivious case.
5 Septembre 2008 - Jeux de colorations dans les graphes - Louis Esperet (Université Charles, Prague)
Résumé : On considère un jeu dans lequel deux joueurs (Alice et Bob) colorient tour à tour les sommets d'un graphe avec un nombre donné de couleurs (de manière à ce que deux sommets adjacents aient des couleurs distinctes). Si à la fin le graphe est entièrement colorié, Alice gagne. Sinon Bob gagne (cela signifie qu'à un moment, un sommet non colorié a toutes les couleurs disponibles dans son voisinage... aucun des deux joueurs ne peut donc le colorier).
Je dirai quelques généralités sur ce jeu introduit par Boadlander en 1991, et on essaiera de voir quelles techniques peuvent être utilisées pour trouver des stratégies gagnantes pour Alice ou pour Bob.