Graphes & Algorithmes
Groupe de Travail



Archives année 2005-2006 Organisateur : Christophe Crespelle


Retour à la page d'accueil du séminaire

29 Septembre 2005:
Christophe PAUL "Décomposition en branches, nouveaux algorithmes"

La largeur de branche  d'un graphe a été introduite par Seymour et al.  début des années 90.  Contrairement à la largeur arborescente, on sait la calculer en temps polynomial sur les graphes planaires (le problème est ouvert pour la largeur arborescente). Ces deux paramètres sont liés, pourtant leurs définitions semblent très différentes. Nous présenterons les liens entre ces deux concepts ainsi qu'un algorithme polynomial pour les graphes d'intervalles.

6 Octobre 2005:
Libre

13 Octobre 2005:
Marie-Catherine Vilarem "Décomposition hyper-arborescentes"

En IA (problèmes de satisfaction de contraintes) et en théorie des bases de données, les structures sous-jacentes sont plutôt des hypergraphes que des graphes. C'est dans ce cadre que Gottlob, Leone, Scarcello ont introduit les notions de
  1. "décomposition généralisée en hyperarbre" et de
  2. "décomposition en hyperarbre"  et les largeurs associées.
Ces deux décompositions sont des décompositions arborescentes, mais la mesure associée est différente : à chaque bloc de la décomposition arborescente, on associe un ensemble d'arêtes de l'hypergraphe qui recouvre le bloc; la largeur est alors le nombre minimum d'arêtes nécessaire pour que chaque bloc soit couvert. De manière analogue à ce qui se passe pour les graphes, les hypergraphes de "largeur en hyperarbre" bornée permettent d'obtenir de larges classes polynomiales pour des problèmes NP-complets en général.

L'exposé est basé essentiellement sur le papier de [Gottlob et al.] à WG 05 : définitions et motivations, liens avec les invariants classiques d'hypergraphes, résultats de complexité.

20 Octobre 2005:
Olivier Gandouet "Sur la complexité de communication"

Soit k un entier et soit \Omega_i des ensembles finis pour tout 1<=i<=k. Soit une fonction f définit de \Omega_1 x \Omega_2x ... x \Omega_k dans {0,1}. <>On a k joueurs (J_1,...,J_k) possédant chacun une puissance de calcul et une mémoire infinie. Chacun des joueurs J_i connait exactement un élément \omega_i de \Omega_i sans avoir aucune information au début du jeu sur les \omega_k pour k différent de i. Ils veulent, en s'envoyant des messages selon une certaines stratégie, réussir à ce que un des joueur puisse gagner le jeu. C'est à dire calculer la valeur exacte de f(\omega_1,...,\omega_n).

On appelle complexité de communication d'une fonction f le minimum de message que les joueurs doivent s'envoyer en utilisant la meilleure stratégie possible sur le pire des cas (ie: le pire des k-uplets \omega_1,...,\omega_n).
Il existe beaucoup de dérivés de la complexité de communication, et entre autre nous nous intéresseront à l'une d'entre eux: la complexité de communication dite probabiliste , ou les joueurs ont cette fois-ci le droit à une stratégie qui inclus de l'aléatoire (par exemple: si le joueur 1 tire PILE alors il communique ces informations au joueur 2, s'il obtient FACE il les communique au joueur 3), ainsi qu'une marge d'erreur sur leur résultat, c'est à dire qu'ils n'ont obligation de retourner le bon résultat qu'avec probabilité supérieur à \alpha>1/2.

Nous verrons que le problème ce décline en beaucoup de sous problème qui semble identique et qui son pourtant différent . Nous verrons aussi qu'il y a des caractéristique commune aux fonction qui sont dans la même classe de complexité , ainsi que les différence entre la complexité probabiliste et celle déterministe.

Si nous avons le temps nous regarderons aussi les outils utilisés pour faire les preuves des résultats obtenus car ils peuvent sans doute étre utilisés pour d'autres types de problèmes.

27 Octobre 2005:
Vacances

3 Novembre 2005:
Journées Graphes-Algo à Bdx

10 Novembre 2005:
Christophe Paul "Sur les k-branches"

Une k-branche est un graphe de branchwidth k arête maximal (l'ajout de tout ensemble d'arêtes augmente la branchwidth). La famille de graphes correspondante pour la notion de treewidth est la famille des k-arbres (une sous-famille de graphes triangulés). Les k-arbres sont caractérisés par la construction suivante: à partir d'une k+1-clique, ajouter succesivement des sommets adjacents à une k-clique.

Nous donnerons une caractérisation des k-branches. Nous montrerons que contrairement aux k-arbres, pour k fixé, il existe une infinité de k-branches minimales (aucun sous-graphe n'est une k-branche). Nous proposerons aussi un algorithme de génération des k-branches.

17 Novembre 2005: Attention !!! 14h30 salle E.323
Stéphane Bessy "Minimum Strong Spanning Sub-digraph"

Le problème suivant est l'analogue orienté de la recherche d'un arbre couvrant dans un graphe non-orienté connexe:

Problème MSSS (Minimum Strong Spanning Sub-digraph):
Instance : D un digraphe fortement connexe.
Question : Trouver un sous-digraphe fortement connexe couvrant D et ayant un nombre minimum d'arcs.

Le problème est NP-difficile, cependant des algorithmes polynomiaux d'approximations sont connus, le meilleur à ce jour réalisant un facteur 1.5 et étant dû à A. Vetta. Par ailleurs, une conjecture proposée en 1995 par J. A. Bondy, affirme qu' il est possible de recouvrir tout digraphe D fortement connexe et de stabilité alpha (D) par au plus alpha (D) circuits, l'union de ces circuits ayant au plus |D|+ alpha (D)) -c arcs, où D désigne le nombre de sommets de D, et c le nombre de composantes connexes de cette union. Ceci étend une question de T. Gallai affirmant que tout digraphe D fortement connexe peut être couvert par alpha (D) circuits.

Avec S. Thomassé, nous prouvons cette dernière conjecture ainsi qu'un corollaire de la conjecture de Bondy : tout digraphe D fortement connexe de stabilité alpha (D) possède un sous-digraphe fortement connexe couvrant ayant au plus |D|+2alpha (D) -2 arcs. Cette construction se fait en temps polynomial, fournissant ainsi une 1+2/alpha (D)/|D|-approximation pour le problème MSSS. L'algorithme présenté ici sera donc utile pour des digraphes denses (alpha (D)<|D|/4).

24 Novembre 2005:
Emeric Gioan "Une ballade touristique dans les matroïdes"

<>Nous survolerons les contrees des matroides et matroides orientes ramifiees de multiples sentiers. Nous apercevrons en vrac et brievement des graphes toujours accompagnes de leur ombre duale (cycles/cocyles), l'algorithme glouton, des alignements de points, quelques dependances lineaires et des faces de polyedres, voire avec un peu de chance des treillis geometriques et un peu de programmation lineaire. Dans un coin on verra peut etre se faufiler le polynome de Tutte et son cortege de proprietes... Puis si ca vous a plus, nous y retournerons dans quelques mois, pour une marche a pied cette fois, en entrant precisement dans le detail des axiomatiques et des constructions.

8 Décembre 2005:
Christophe Crespelle "Triangulations minimales des graphes de permutation"

D'après un article de Daniel Meister, nous verrons comment trouver dans le réaliseur d'un graphe de permutation, à la fois les séparateurs minimaux de ce graphe et les cliques maximales potentielles. Nous verrons comment l'auteur utilise ces résultats pour construire en O(n+m) une structure permettant de représenter toutes les triangulations minimales d'un graphe de permutation. Cette structure autorise en particulier le calcul de la Tree Width et du Minimum Fill-in du graphe donné en temps O(n+m).
 

15 Décembre 2005:
Joanna Mouleyrac "Autour du problème de multicast"

Le multicast a été proposé par Deering en 1991 pour permettre de développer plus efficacement des applications telles que la vidéoconference. Pourtant, depuis lors, cette solution n'est pas encore bien déployée dans Internet. Deux  problèmes principaux  freinent son déploiement. Premièrement il y a le problème du passage à l'échelle du nombre d'entrées de routage stoquées dans les routeurs. En effet, en Multicast, un arbre est stoqué par groupe et comme le nombre de groupes augmente de façon importante, la mémoire des routeurs risque d'être saturée et le routage ralenti. Deuxièmement, le nombre important d'arbres multicast implique des messages de contrôle qui inondent et perturbent le réseau.

C'est pour cela que l'agrégation d'arbres a été proposée en 2001. L'idée principale de l'agrégation d'arbres est de permettre à plusieurs groupes multicast d'utiliser le même arbre de routage. Ainsi, à un arbre conrrespondent plusieurs groupes et le nombre d'entrées est diminuié ainsi que le nombre de messages de contrôle. Le principal problème de l'agrégation d'arbre est de trouver, pour un groupe donné, un arbre qui pourra être utilisé et qui existe déjà. On peut envisager d'utiliser pour un groupe donné un arbre qui couvre plus de membres que prévu. Dans ce cas, un peu de bande-passante est perdu lorsque les non-destinataires reçoivent les paquets mais le nombre d'entrées de routage est réduit.

Pourtant, cette solution n'est pas appliquable aux grands domaines. En effet, il devient alors très dur de trouver un arbre qui existe déjà et qui puisse couvrir le groupe. Dans des grands domaines, le nombre d'arbres différents est très important et la probabilité d'en trouver un qui correspond est très faible. C'est pourquoi nous proposons un algorithme spécifique aux grands domaines. Nous effectuons un découpage préalable du domaine en sous-domaines afin d'effectuer l'agrégation séparément dans chacun des sous-domaines. Les sous-domaines contenant moins de noeuds, l'agrégation est rendue possible et le nombre d'entrées est finalement réduit.

5 Janvier 2006:
Libre

12 Janvier 2006:
Annulé

19 Janvier 2006: Comité d'évaluation LIRMM

26 Janvier 2006:
Binh-Minh Bui-Xuan " Ptolemaic graphs "

Pour ce début de 2006 je vous présenterai un modèle d'intersection pour la classe des "Ptolemaic graphs" et les potentiels qui en découlent. Ce résultat revient aux récents travaux de R. Uehara et Y. Uno. Il est disponible dans les actes de ISAAC'05.
La classe des "Ptolemaic graphs" est l'intersection de celle des graphes triangulés et celle des graphes distance-héréditaires.

26 Janvier 2006:
François Boutin " Filtrage et clustering pour les graphes du monde réel "

7 Juin 2006:
Derek G. Corneil " Graph searching with an emphasis on Lexicographic Breadth First Search (LBFS) "

Recently there has been a great deal of attention on the use of LBFS for various problems such as the recognition of specific graph families and diameter approximation. The proofs of correction of these algorithms often employ a four vertex characterization of LBFS. This talk provides a survey of recent results on LBFS and then develops similar four vertex characterizations for other graph searches such as BFS and DFS. These characterizations lead to the discovery of new searches, Lexicographic DFS and Maximal Neighbourhood Search.

8 Juin 2006
Martin Charles Golumbic " Rank-Tolerance Graph Classes "
Caesarea Rothschild Institute, University of Haifa, Israel

In this talk we introduce certain classes of graphs that generalize &phi -tolerance chain graphs. In a rank-tolerance representation of a graph, each vertex is assigned two parameters: a rank, which represents the size of that vertex, and a tolerance which represents an allowed extent of conflict with other vertices. Two vertices are adjacent if and only if their joint rank exceeds (or equals) their joint tolerance.
This paper is concerned with investigating the graph classes that arise from a variety of functions, such as min, max, sum, and prod (product), that may be used as the coupling functions &phi and &rho to define the joint tolerance and the joint rank. Our goal is to obtain basic properties of the graph classes from basic properties of the coupling functions.
We prove a skew symmetry result that when either &phi or &rho is continuous and weakly increasing, the (&phi,&rho)-representable graphs equal the complements of the (&rho,&phi)-representable graphs. In the case where either &phi or &rho is Archimedean or dual Archimedean, the class contains all threshold graphs. We also show that, for min, max, sum, prod (product) and, in fact, for any piecewise polynomial &phi, there are infinitely many split graphs which fail to be representable.
In the reflexive case (where &phi=&rho), we show that if &phi is nondecreasing, weakly increasing and associative, the class obtained is precisely the threshold graphs. This extends a result of Jacobson, McMorris, and Mulder for the function min to a much wider class, including max, sum, and prod.
We also give results for homogeneous functions, powers of sums, and linear combinations of min and max.

Keywords: tolerance graphs, interval graphs, threshold graphs, Archimedean functions, Warren's theorem, &phi -tolerance chain graphs

(Joint work with Robert E. Jamison, Clemson University, USA.)

15 Juin 2006
Emeric Gioan " Suites de degrés, orientations de graphes à renversements près de cycles et cocycles, et polynôme de Tutte "

On considère que deux orientations d'un graphe sont équivalentes si elles s'obtiennent mutuellement par une suite de renversements de cycles, resp. de cocycles, resp. de cycles ou de cocycles. Dans chaque cas, on établit des relations, bijectives de préférence, entre l'ensemble des classes d'équivalence obtenues et l'ensemble des suites de degrés des orientations du graphe. Et on énumère ces classes et ces suites a l'aide d'évaluations du polynôme de Tutte du graphe (généralisation du polynôme chromatique à deux variables duales). Il en ressort des questions plus ou moins ouvertes en liaison avec le modèle du tas de sable.