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
- "décomposition généralisée en
hyperarbre" et de
- "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.
|