BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230228T100000
DTEND;TZID=Europe/Paris:20230228T120000
DTSTAMP:20260423T135542
CREATED:20230125T165233Z
LAST-MODIFIED:20230224T142635Z
UID:11085-1677578400-1677585600@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Algorithmes pour la Dimension Métrique dans les graphes dirigés » Antoine Dailly (LIMOS\, Univ. Clermont-Ferrand)
DESCRIPTION:Résumé :\nLe problème de la Dimension Métrique d’un graphe se pose de la façon suivante : on cherche un ensemble R de sommets de taille minimale tel que\, pour toute paire de sommets du graphe\, il existe un sommet de R dont les distances aux deux sommets de la paire sont distinctes. Ce problème a été principalement étudié dans les graphes non-dirigés\, et il a attiré l’attention ces dernières années\, notamment en raison de sa difficulté : il est NP-complet et son meilleur facteur d’approximation en temps polynomial est log(n)\, y compris sur des classes de graphes très restreintes. \nNous considérons ce problèmes dans les graphes dirigés et orientés (la différence est que les graphes dirigés peuvent contenir des 2-cycles\, au contraire des graphes orientés)\, pour lesquels la Dimension Métrique a été récemment étudiée. Nous montrons que le problème reste NP-dur\, même dans les graphes orientés planaires bipartis de degré maximum 6. Cependant\, nous donnons des algorithmes linéaires résolvant le problème sur les arbres dirigés (les graphes dirigés dont le graphe sous-jacent est un arbre) et les orientations de graphes unicycliques. Enfin\, nous avons un algorithme paramétré par la largeur modulaire. \n\nAbstract:\nIn graph theory\, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices\, such that for any pair of vertices of the graph\, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem has mainly been studied on undirected graphs\, and has gained a lot of attention in recent years\, mainly because of its difficulty: it is NP-complete and has a best polynomial-time approximation factor of log(n) even on very restricted graph classes. \nWe focus our study on directed and oriented graphs (the difference is that directed graphs may contain 2-cycles\, unlike oriented graphs)\, for which the Metric Dimension has been recently studied. We prove that Metric Dimension remains NP-hard\, even on planar bipartite oriented graphs of maximum degree 6. However\, we find linear-time algorithms solving the problem on directed trees (directed graphs whose underlying graph is a tree) and on orientations of unicyclic graphs. Finally\, we give a fixed-parameter-tractable algorithm for directed graphs when parameterised by modular-width.
URL:https://www.greyc.fr/event/seminaire-algorithmique-antoine-dailly-limos-univ-clermont-ferrand/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR