Séminaire

Le 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.

Nous 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 sans circuit planaires 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.

https://daillya.github.io/

Lien séminaire : https://us02web.zoom.us/j/8519510325?pwd=NjZPUFBuWXhIZG9YUVVWQ0M0SUtTZz09