Comment appliquer les chaînes augmentantes pour atterrir a l'heure ?

Description

Lorsqu'un avion approche d'un aéroport , il dispose d'un intervalle de temps (slot) très limité (une vingtaine de minutes) pour atterrir. Si l'avion a du retard à cause des conditions météorologiques (à cause du retard d'autres avions, ou si lui-même a eu du retard au décollage), il perd son slot et il faut qu'un nouveau slot lui soit attribué par les contrôleurs des opérations de la compagnie aérienne. Cependant, les slots d'atterrissage sont une denrée rare et, pour qu'un avion A puisse atterrir a l'heure, les contrôleurs doivent régulìèrement modifier l'attribution des slots d'autres avions afin d'affecter un slot compatible avec l'heure d'arrivée de l'avion A. Ce problème peut aisément etre modélisé comme un problème de couplage dans un graphe biparti. Malheureusement, dû au système mis en place pour permettre ces échanges, les contrôleurs aériens ne peuvent effectuer leurs modifications qu'en effectuant deux types d'opérations : soit attribuer à l'avion A un slot libre, soit donner à l'avion A le slot d'un avion B et attribuer un slot libre à ce dernier. Le problème devient donc le suivant. Soit G un graphe et M un couplage (ensemble d'arêtes deux-à-deux disjointes) de G. Comment calculer un couplage maximum pouvant etre obtenu à partir de M en utilisant uniquement des chemins augmentants de longueur au plus k ? Ce problème a déjà été étudié dans le cadre des réseaux sans-fil car il fournit une simple approximation au problème de couplage maximum. Nous prouvons que, pour k = 3, ce problème peut être résolu en temps polynomial, fournissant ainsi un algorithme efficace pour les contrôleurs aériens. Nous prouvons ensuite que, pour tout entier impair k ≥ 5, le problème est NP-complet dans les graphes bipartis planaires de degré au plus 3.

Abstract

International audience

Additional details