Séminaire

Possibilité de visio-conférence @IP : 193.55.95.10 Nom du correspondant technique : Nicolas CHAMPEIL Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26 nicolas.champeil@isima.fr Tél salle de visio : 04 73 40 50 47 Motivés initialement par des questions algorithmiques autour de la subdivision de digraphes, nous définissons la notion de graphe orienté antistrong (par opposition à strong -fortement connexe-). Un graphe orienté est antistrong si tout couple de points peut être relié par un parcours orienté alternant. La (bonne) caractérisation d’un graphe antistrong est que son graphe biparti d’adjacence est connexe. On s’est intéressé principalement à des questions algorithmiques autour de cette notion. Certaines découlent facilement de la caractérisation précédente, d’autres sont plus difficiles à établir. Des techniques matroïdales ont notamment été utiles pour obtenir certains résultats. Au cours de cet exposé, je motiverai et présenterai ces différents résultats.