retour
Résumés des exposés
version postscript
Pascal Auillans et Olivier Baudon
LaBRI, Université Bordeaux 1
auillans@labri.fr, baudon@labri.fr
Orateur : Pascal Auillans.
Fractionnement de grands graphes issus de réseaux sémantiques.
Résumé
Notre travail s'inscrit dans le contexte d'une nouvelle norme
d'indexation de document appelée XTM (XML topic maps).
Cette norme, définie par une grammaire en XML permet
l'indexation de documents, la définition de relations entre les
indexes et la sémantisation de ces relations.
Cette norme permet donc la construction d'un hypergraphe étiqueté
d'index. Nous nous intéressons donc à divers problèmes
de la théorie de graphes pour répondre aux besoins des utilisateurs
de cette nouvelle norme. Ainsi nous étudions pour le moment des
problèmes de fractionnement de graphes en un minimum de sous-graphes
induits de rayon ou de diamètre bornés.
Ces problèmes (k-domination pour le rayon, partitionnement
en k-cliques pour le diamètre) sont connus pour être NP-complets.
Nous cherchons donc des heuristiques ayant une complexité linéaire
permettant de traiter des grands graphes, en moyenne d'ordre 1 million,
et offrant des réponses satisfaisantes.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Bruno Bachelet et Philippe Mahey
LIMOS, FRE 2239 - CNRS
bachelet@isima.fr, mahey@isima.fr
Orateur : Bruno Bachelet.
Documents hypermedia synchronisés et problèmes de tension
dans un graphe.
Résumé
Tout le monde connaît maintenant le HTML qui est le langage
favori pour la diffusion de documents sur Internet. Il apporte de nouvelles
possibilités par rapport au support papier grâce à
ses possibilités d'interactivité et à son intégration
du multimédia. Mais comme toujours, les besoins augmentent et de
nouveaux langages sont développés pour améliorer la
structure et l'interactivité des documents. Notamment des langages
comme SMIL (Synchronized Multimedia Integration Language) ont fait son
apparition. Ils offrent une nouvelle dynamique aux documents hypermédia,
et en particulier la possibilité d'y animer et synchroniser des
composants multimédia.
La variété des composants qui forment un document
(audio, vidéo, texte, image...) font de l'animation un problème
compliqué. L'auteur d'un document synchronisé fournit une
liste de contraintes temporelles sur les composants de manière à
décrire le déroulement de la présentation. Ces composants
ont chacun une durée de présentation qui est flexible dans
une certaine limite.
Tout le problème consiste à trouver un bon ajustement
des durées pour que la présentation se déroule au
plus proche de ce que souhaite l'auteur tout en évitant les pauses.
Ce problème peut se modéliser, après quelques restrictions,
comme un problème de tension de coût minimum dans un graphe.
Pour le résoudre, nous proposons une adaptation de l'algorithme
"out-of-kilter" dans le cas de coûts linéaires par morceaux
et dans le cas
de coûts non linéaires convexes. Des tests numériques
montrent l'intérêt de cette modélisation pour l'optimisation
de la qualité de présentation dedocuments hypermédia.
Enfin, nous terminerons avec la présentation d'une classe de graphes
particulière, les graphes série-parallèles, qui représentent
une idéalisation du problème.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Mourad Baïou
Laboratoire
LIMOS, FRE CNRS 2239
Université Blaise Pascal, Clermont II
baiou@isima.fr
En collaboration avec :
Michel Balinski
CNRS and Ecole Polytechnique
Laboratoire d'Econométrie, 1 rue Descartes, 75005 Paris, France.
balinski@poly.polytechnique.fr
Orateur : Mourad Baiou
Le problème d'allocation stable
Résumé
Le problème d'allocation stable généralise
les problèmes d'affectations stables (``one-to-one,'' ``one-to-many,''
ou ``many-to-many'') à l'attribution de quantités réelles
ou d'heures. Un algorithme fortement polynomial établit l'existence
d'allocations stables.
Il est montré que l'ensemble des allocations stables
est un treillis distributif en général ; mais dans le cas
``nondégénéré'' il forme un un ordre linéaire
total. Dans le cas générique, quand un problème est
``fortement nondégénéré,'' il existe une unique
allocation stable.
Un algorithme simple donne l'allocation stable optimale par
lignes et l'allocation stable optimale par colonnes. Quand un problème
est
nondégénéré l'algorithme produit toutes
les allocations stables.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Anne Berry
LIMOS FRE CNRS 2239
Université Blaise Pascal, Clermont II
berry@isima.fr
Orateur : Anne Berry
Triangulations et faibles triangulations.
Résumé
Depuis les années 70, on sait plonger en temps polynomial
un graphe quelconque dans un triangulé par ajout d'un ensemble d'arêtes
qui est minimal au sens de l'inclusion (triangulation minimale).
Ce procédé de plongement est utile pour de nombreuses
applications informatiques; il s'avère également très
intéressant du point de vue structurel, grâce aux invariants
algorithmiques mis en évidence par la suite.
Pour explorer de nouvelles voies de recherche, nous définissons
un procédé de triangulation "maximale" qui se fait par retrait
plutôt que par ajout d'arêtes, et proposons un algorithme polynomial
correspondant.
Nous nous préoccupons ensuite d'étendre ces deux
procédés au plongement d'un graphe quelconque dans un graphe
faiblement triangulé : les g.f.t. sont une surclasse des triangulés
pour lesquels on a mis en évidence ces dernières années
une structure proche de celle des
triangulés.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Nicolas Bonichon, Bertrand Le Saec et Mohamed Mosbah
LaBRI, Bordeaux
bonichon@labri.fr, lesaec@labri.fr, mosbah@labri.fr
Orateur : Nicolas Bonichon
Realizers : théorème de Wagner et nombre de noeuds internes.
Résumé
Un realizer d'un graphe planaire maximal est un ensemble de
3 arbres recouvrants T0, T1 et T2 satisfaisant certaines propriétés
structuelles.
Cette structure de données a été utilisé
dansde nombreux algorithmes de dessins de graphes.
Nous proposons un système de réécriture
sur les realizers composé de 4 règles : 2 règles (S+
et S-) de recolorations de 3-cycles tricolores, c'est à dire avec
une arête dans chaque arbre, ainsi que 2 règles (f1 et f2)
de "flips diagonaux coloriés". Ce système généralise
aux réalizers le théorème de Wagner : soit R1 (resp.
R2) un realizer d'un graph planaire maximal G1 (resp.G2). Il existe une
séquence d'opérations (S+|S-|f1|f2)* transformant R1 en R2.
En utilisant ce système, nous montrons aussi que \xi_0
+ \xi_1 + \xi_2 - \Delta = n-1.
ou \xi_i correspond au nombre de noeuds internes dans l'abre Ti et
Delta correspond au nombre de faces tricolores du realizer.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Vincent Bouchitté, Frédéric Mazoit et Ioan Todinca
LIP, ENS-Lyon
LIFO, Université d'Orléans.
vbouchit@ens-lyon.fr, fmazoit@ens-lyon.fr, Ioan.Todinca@lifo.univ-orleans.fr
Orateur : Frédéric Mazoit.
Sur la largeur arborescente d'un graphe planaire et de son dual.
Résumé
Nous donnons une preuve simple d'un resultat obtenu par D. Lapoire,
à savoir : la largeur arborescente d'un graphe planaire et celle
de son dual diffèrent d'au plus un.
Pour cela, nous interprétons les séparateurs minimaux
du graphe par des courbes de Jordan. A l'aide de ces courbes, nous définissons
la notion de région-bloc et montrons que cette notion correspond
à la notion de bloc au sens des triangulations minimales (à
la Robertson-Seymour).
Ensuite, nous montrons comment a partir d'une triangulation
du graphe construire une triangulation du dual dont la largeur depasse
celle du graphe d'au plus un.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Marie-Eliette Dury
Laboratoire de Mathématiques Appliquées
Université Blaise Pascal, Clermont II
Marie-Eliette.Dury@math.univ-bpclermont.fr
Orateur : Marie-Eliette Dury
Arbres de percolation pour des processus symétriques stables autosimilaires
à accroissements stationnaires.
Résumé
Les processus sym\étriques alpha-stables (0<alpha <2)
autosimilaires à accroissements stationnaires fournissent des modèles
stochastiques dans de nombreux domaines (économie,...). Nous pouvons
citer parmi ceux-ci les représentations dites à moyenne mobile
ou harmonisable (selon la dénomination de Samorodnitsky et Taqqu
[4]). Ils admettent une décomposition en ondelettes [3]. L'ensemble
des ondelettes a pour ensemble codant }Z\times Z^{d}\times E_{d}^{\ast
} où E_{d}^{\ast }=\{0,1\}^{d}\backslash (0,...,0) Cet ensemble
a une structure d'arbre
On peut choisir de sommer les termes de cette décomposition
sur un sous-arbre de percolation. On obtient ainsi un modèle d'intermittence
identifiable qui generalise les modèles gaussiens [1], ou stables.
On peut alors estimer indépendemment le paramètre
de percolation }P provenant du sous-arbre de percolation utilisé
et le paramètre d'autosimilarité H (0<H<1) au moyen
de deux p -variations distinctes (0<p<alpha ) [2].
Références
[1] Benassi A., Cohen S., Deguy S., Istas J., ICBM, conference
on wavelets, Floride (1998).
[2] Dury M-E., Identification of Self-similar Symmetric Stable Processes
with Stationary Increments, (preprint 00-18 LMA).
[3] Meyer Y., Ondelettes et Op\'{e}rateurs, Hermann (1990)
[4] Samorodnitsky G., Taqqu M.S., Stable Non-Gaussian Random Processes:
Stochastic Models with Infinite Variance, Chapman-Hall (1994).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Pierre Fouilhoux et A. Ridha Mahjoub
Laboratoire LIMOS, CNRS
Université de Clermont II, 63177 Aubière, France
Fouilhoux@turing.univ-bpclermont.fr, Ridha.Mahjoub@math.univ-bpclermont.fr
Orateur : Pierre Fouilhoux
Via Minimization et problème du sous-graphe biparti induit.
Résumé
Soit G=(V,E) un graphe. Si W\subset V, alors E(W) représente
l'ensemble des arêtes de G dont les deux extrémités
sont dans W. Etant donnée une fonction poids c:V\rightarrow \mathbb{R}qui
associe à chaque sommet v un poids c(v), le problème
du sous-graphe biparti induit consiste à rechercher un sous-graphe
biparti induit (W,E(W)) de G tel que c(W)=\sum_{v\in W} c(v) soit maximum.
Nous montrons d'abord que le problème dit de Via Minimizatio
se ramène à ce problème. Nous étudions par
la suite la structure faciale du polytope associé aux solutions
du problème du sous-graphe biparti induit. Nous identifions différentes
classes d'inégalités valides
pour ce polytope et décrivons des conditions nécessaires
et suffisantes pour que ces inégalités définissent
des facettes. Pour certaines de ces inégalités, nous décrivons
des algorithmes polynomiaux de séparation. Nous donnons également
certaines méthodes de construction de facettes, celles-ci concernent
en particulier des opérations d'ajouts de graphes complets, d'éclatements
de sommets et de subdvisions d'étoiles.
Mots clés : sous-graphe biparti induit, polytope, facette,
algorithme de séparation.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Simone Dantas de Souza, Sylvain Gravier et Frédéric Maffray
Orateur : Sylvain Gravier (IMAG)
Graphes extremaux pour la version liste d'un theoreme Nordhaus-Gaddum.
Résumé
On caractérise la structure des graphes G =(V, E) tels
que Ch(G)+Ch({\bar G})=| V|+1, où Ch(G) est le nombre chromatique
de liste de G.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Mekkia Kouider
Sur le nombre b-chromatique
Résumé
Le nombre b-chromatique d'un graphe G=(X,E)
est le maximum de couleurs k utilisables dans une coloration
propre de X, coloration telle que chaque
couleur i a au moins un représentant
x(i) dont le voisinage est coloré par les ( k-1) autres
couleurs.
Nous donnons des bornes pour le nombre b-chromatique en fonction d'autres
paramètres; et d'autre part nous
étudions le nombre b-chromatique d'une somme cartésienne,
et enfin la relation entre
le nombre b-chromatique d'un sous graphe et celui du graphe.
Une partie de ce travail est réalisée en collaboration
avec Maryvonne Maheo.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Jean-Marc Lanlignel
LIRMM, Montpellier
lanligne@lirmm.fr
Orateur : Jean-Marc Lanlignel
Autour de la décomposition en coupes.
Résumé
La décomposition en coupes, introduite par Cunningham
en 1982, est une généralisation intéressante de la
décomposition modulaire, peut-être moins connue qu'elle ne
le mérite. Peu de résultats nouveaux seront donnés
dans cet exposé : il s'agit principalement, au travers des parallèles
entre cette décomposition et la décomposition modulaire (propriétés
des graphes totalement décomposables et des graphes indécomposables),
de faire découvrir cet outil.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Fabien de Montgolfier
LIRMM, Montpellier
montgolf@lirmm.fr
Orateur : Fabien de Montgolfier
Décomposition modulaire des graphes orientés: un algorithme
linéaire.
Résumé
La décomposition modulaire des graphes joue un rôle important
en théorie des graphes, par les approches du type <<diviser
pour regner>>
qu'elle permet. Des algorithmes en O(n+m) existent pour décomposer
les graphes non-orientés. En revanche à notre connaissance
les meilleurs algorithmes pour le cas orientés sont en O(n+mlog
n). Je propose ici une réduction au cas non-orienté, réalisable
en O(n+m) : en manipulant les arbres de décomposition de deux graphes
non-orientés auxilliaires, on peut retrouver la décomposition
du graphe orienté originel.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Arnaud Pecher
LIFO, Orléans
Arnaud.Pecher@lifo.univ-orleans.fr
Orateur : Arnaud Pecher
Deux méthodes pour construire des graphes partitionnables.
Résumé
Pour l'étude de la célèbre conjecture forte
des graphes parfaits, il est utile d'exhiber des méthodes pour construire
des graphes partitionnables. Nous donnons deux telles méthodes.
La première repose sur une modification de deux des cliques maximums
d'un graphe partitionnable donné. La seconde décrit l'impact
de la première sur l'ensemble des stables maximums de ce même
graphe.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Bernard Fortz, A. Ridha Mahjoub et Pierre Pesneau
Université Catholique de Louvain
Institut d'Administration et de Gestion, Louvain-la-Neuve, Beglgium
et
LIMOS, CNRS FRE 2239
Université Blaise Pascal, Clermont Ferrand, France
Ridha.Mahjoub@math.univ-bpclermont.fr, pesneau@turing.univ-bpclermont.fr
Orateur : Pierre Pesneau
Le problème du sous-graphe 2-arête connexe avec des cycles
bornés.
Résumé
Un graphe G=(V,E) est dit 2-arête connexe s'il existe
au moins deux chaî nes arête-disjointes entre chaque paires
de sommets de V. Soit G=(V,E) un graphe avec des poids sur les ar\^etes
et un entier K \geq 3. Le problème du sous-graphe 2-arête
connexe avec contraintes de cycles est de trouver un sous-graphe H=(V,F)
2-arête connexe de poids minimum tel que chaque arête de F
appartienne à un cycle de taille inférieure ou égale
à K. Ce problème a des applications dans la conception de
réseaux de télécommunictaion fiables.
Dans ce papier, nous étudions ce problème d'un
point de vue polyédral. Nous donnons tout d'abord une formulation
du problème sous forme d'un programme en nombres entiers en utilisant
les variables naturelles. A notre connaissance, celle-ci est la première
formulation en 0-1 de ce problème utilisant uniquement ces variables.
Nous discutons également de plusieurs classes d'inégalités
valides pour le polytope associé. Nous déterminons la dimension
de ce polytope et nous donnons enfin des conditions nécessaires
et suffisantes pour que ces contraintes définissent des facettes.
mots clefs : sous-graphe 2-arête connexe, cycles bornés,
polytope, facette.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Olivier Raynaud
LIRMM, Montpellier
raynaud@lirmm.fr
Orateur : Olivier Raynaud
Un algorithme de calcul d'une 4-approximation de la 2-dimension des arbres.
Résumé
Les performances des langages objets typés dynamiquement
sont fortement liées aux techniques utilisées pour résoudre
le problème de la sélection de méthode. Lorsqu'une
fonction générique est invoquée, nous devons pouvoir
déterminer efficacement quelle est la méthode à appliquer.
Les solutions proposées à ce jour restent coûteuses
en termes d'espace. Afin de réduire cet espace, nous proposons de
coder la hiérarchie de type par des vecteurs de bits. D'un point
de vue théorique, la recherche de la taille minimale de ces vecteurs
revient au calcul de la 2-dimension d'un ordre (Bouchet 84). Ce problème
très difficile est malheureusement NP-complet dans le cas général
(Stahl 84). L'obtention d'un codage compact est donc soumise à l'élaboration
d'algorithmes d'approximation.
Dans le cadre d'une relation d'héritage et de sous-typage
simple, la hiérarchie de classe adopte la forme d'un arbre. Sur
cette classe particulière des ordres nous ne savons pas si le problème
du calcul de la 2-dimension reste NP-complet. Nous ne savions pas non plus
s'il admettait des algorithmes de r(n)-approximation. Dans cet exposé,
nous proposons un algorithme efficace, appelé ``dichotomique'',
de calcul d'un codage compact des arbres. Nous montrons, de plus, que notre
algorithme calcul, à un facteur constant 4 près, la 2-dimension
exacte des instances arborées.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
András Sebõ
CNRS, Leibniz-IMAG, Grenoble
Andras.Sebo@imag.fr
Orateur : András Sebõ
Quelques problèmes combinatoires concernant les nombres.
Résumé
Je vais présenter quelques problèmes combinatoires
qui se sont montrés en étudiant des problèmes de graphes,
ou de combinatoire poliédrale. Des problmèmes variés
trouvent des formulations communes en utilisant des inégalités
mélangés avec des classes de congruences modulo D.
Les questions que nous posons sont typiquement combinatoires,
élémentaires, mais la solution de certains peut être
difficile. Pour la plupart je ne sais pas dire plus que des conjectures,
et des résultats particuliers, qui cependant trouvent des applications.
Parmi les problèmes traités nous retrouverons le 'coureur
solitaire', les bases Hilbertiennes, les simplexes vides et leur largeur,
et de nouveaux problèmes avec des nouvelles connexions (à
des séries de Skolem, Sturm, et Beatty).
Voici un problème et deux conjectures à titre
d'exemples :
Etant donnés les nombres a_1, ... , a_n dénominateurs
D dans l'interval (0,1)
et le nombre 0<k<D, sous quelles conditions (`facilement
vérifiables') est il vrai que
pour tout i=1,
... , D-1 :
{ia_1} + ... + {ia_n}
\ge k , où { } note la partie fractionaire.
Conjecture : Si n est pair, k=n/2 et a_1 < ... <
a_n, alors il est nécessaire
et suffisant que a_i + a_{n-i} = 1 , i=1,..., n/2
.
Une autre conjecture (plus anciennne, posée par Cusick
et Wills, indépendemment et redécouverte par Goddyn et Tarsi)
: Si n coureurs partent en même temps du même endroit, et courent
avec des vitessesses constantes différentes sur une piste circulaire,
alors pour tout coureur donné il existe un moment quand sa distance
est au moins 1/n de tous les autres. Ce dernier a des conséquences
en théorie des graphes, et en même temps peut être formulé
en utilisant le `language' du problème précédent ...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Jamel Dammak1, Gerard LOPEZ2, Maurice POUZET3
et Hamza SI KADDOUR3
1Faculté des Sciences de Sfax, Tunisie
2Institut de Mathématiques de Luminy
3 LaPCS Université Claude Bernard Lyon1
Orateur : Hamza Si Kaddour
Demi-reconstruction des graphes finis.
Résumé
Les graphes considérés sont simples et non orientés.
Soient G et G' deux graphes ayant le même ensemble de
sommets V. On dit que :
- G et G' sont demi-isomorphes si G' est isomorphe à
G ou à \overline G, le graphe complément de G.
- G et G' sont k-demi-isomorphe si pour toute partie X
de V de cardinal k, G[X] et G'[X] sont demi-isomorphes, où
G[X] est le sous-graphe de G induit par X.
Un graphe G est dit k-demi-reconstructible si tout
graphe G', k-demi-isomorphe à G, est demi-isomorphe à G.
Pierre Ille a posé le problème suivant : Quel est le plus
petit entier h tel que tout graphe ayant un nombre suffisamment grand de
sommets soit h-demi-reconstructible ?
Nous montrons que h=4, plus precisément si G et
G' sont k-demi-isomorphes sur le même ensemble à n sommets
avec 4\leq k\leq n-4
alors G'=G ou G'=\overline G.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Anne Berry, Alain Sigayret et Christine Sinoquet
LIMOS CNRS FRE 2239
Université Blaise Pascal Clermont II
et
Laboratoire AMS, UMR 1095 INRA,
Université Blaise Pascal Clermont II
berry@isima.fr, sigayret@isima.fr, Christine.Sinoquet@univ-bpclermont.fr
Orateur : Christine Sinoquet
Représentation d'une phylogénie par une famille de graphes.
Résumé
En biologie, dans de nombreux domaines, on dispose de matrices
de dissimilarités issues de la comparaison de séquences génomiques.
A partir de ces matrices, les biologistes cherchent à reconstituer
un arbre d'évolution (phylogénie).
La succession des seuils de la matrice définit une famille
de graphes triangulés emboîtés les uns dans les autres.
Nous mettons en évidence des invariants structurels valables
pour tous les graphes d'une telle famille et établissons des rapports
avec la topologie de l'arbre d'évolution.
Nous appliquons cette théorie aux données inexactes
issues des expérimentations.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Vincent Bouchitté, Dieter Kratsch, Haiko Müller, Ioan Todinca
Orateur : Ioan Todinca
Sur l'approximation de la largeur arborescente.
Résumé
Le calcul de la largeur arborescente des graphes est un probleme
NP-difficile, même pour des classes de graphes très
particulières, comme les graphes sans triplet astéroïde.
Nous étudions une heuristique qui calcule une triangulation
minimale d'un graphe par complétion successive des séparateurs
de cardinal minimum. Nous montrons que, pour les graphes de nombre
astéroïde borné, la largeur arborescente de la triangulation
ainsi obtenue approxime la largeur arborescente du graphe en entrée
à une constante multiplicative près.
retour