Unité mixte de recherche 7235

A Polynomial Time Algorithm For Finding The Longest Simple Path In A Complete Graph

Pierre Cayet

Dans cet article de théorie des graphes, nous proposons un ensemble d’outils originaux permettant de construire de manière systématique l’ensemble des chemins associés à un graphe. Nous démontrons un ensemble de propriétés permettant de formuler facilement et récursivement cet ensemble de chemins, avant de présenter un algorithme permettant d’identifier un sous-ensemble de chemins en temps polynomial, dont on démontre ensuite qu’il inclut par définition le chemin le plus long. Nous montrons ensuite qu’il est possible de reformuler le problème du plus long chemin simple dans un graphe complet par quelques légères modifications de cet algorithme. Cet article, a l’apport principalement théorique, a des applications évidentes dans l’étude des réseaux, qu’ils soient électriques, gaziers, de transport ou autre.

AGENDA

jeudi 8 décembre 2022

Lunch

Georges Prat

12h - 13h, salle 110

Modeling ex-ante risk premiums in the oil market

lundi 12 décembre 2022

Law, Institutions and Economics in Nanterre (LIEN)

Clément Brébion (Copenhagen BS)

En salle 614 et en distanciel

Unemployment Insurance Eligibility and Employment Duration

mardi 13 décembre 2022

Développement Durable Environnement et Energie (DDEE)

Nicolas Astier (Paris School of Economics)

16h-17h

Riding together: eliciting travelers’ preferences for long-distance carpooling

mercredi 14 décembre 2022

Économies du monde musulman

Mohamed Touati Tliba (École Supérieure de Commerce, Alger)

The scientific wealth of nations with special reference to MENA region: a cross-country productivity analysis of academic research

jeudi 15 décembre 2022

Doctorants

Pablo Aguilar Perez

Profitability and solvency of French insurance companies in an environment of low interest rates

jeudi 15 décembre 2022

Groupe de travail « Intelligence artificielle »

Matthieu Latapy (LiP6, CNRS / Sorbonne Université)

Salle G614B

Résistance — Perturber les Infrastructures en Réseaux

jeudi 15 décembre 2022

Groupe de travail Economie Comportementale

Magali Dumontet

TBA

jeudi 5 janvier 2023

Lunch

Mehdi Aït-Hamlat, Florian Baudoin, Tanguy Bonnet

Nouveaux doctorants

Inscription aux Newsletters