Recovery of disrupted airline operations using k-Maximum Matching in Graphs

Nicolas Nisse 1 Alexandre Salch 2 Valentin Weber 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : When an aircraft is approaching an airport, it gets a short time interval (called {\it slot}) that it can use to land. If the landing of the aircraft is delayed (because of bad weather, or if it arrives late, or if other aircrafts have to land first), it looses its slot and Air traffic controllers have to assign it a new slot. However, slots for landing are a scare resource of the airports and, to avoid that an aircraft waits too much time, Air traffic controllers have to regularly modify the assignment of the slots of the aircrafts. Unfortunately, for legal and economical reasons, Air traffic controllers can modify the slot-assignment only using two kind of operations: either assign to aircraft $A$ a slot that was free, or give to $A$ the slot of another aircraft $B$ and assign to $B$ a free slot. The problem is then the following. Let $k\geq 1$ be an odd integer and let $G$ be a graph and $M$ be a matching (set of pairwise disjoint edges) of $G$. What is the maximum size of a matching that can be obtained from $M$ by using only augmenting paths of length at most $k$? Moreover, how to compute such a maximum matching? This problem has already been studied in the context of wireless networks, mainly because it provides a simple approximation for the classical matching problem. We prove that this problem can be solved in polynomial-time when $k\leq 3$. Then, we show that, for any odd integer $k\geq 5$, the problem is NP-complete in planar bipartite graphs with maximum degree at most $3$.
Type de document :
[Research Report] RR-8679, Inria Sophia Antipolis; INRIA. 2015
Liste complète des métadonnées
Contributeur : Nicolas Nisse <>
Soumis le : mardi 17 février 2015 - 17:59:15
Dernière modification le : samedi 17 septembre 2016 - 01:36:46
Document(s) archivé(s) le : mardi 26 mai 2015 - 11:25:35


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01116487, version 1



Nicolas Nisse, Alexandre Salch, Valentin Weber. Recovery of disrupted airline operations using k-Maximum Matching in Graphs. [Research Report] RR-8679, Inria Sophia Antipolis; INRIA. 2015. <hal-01116487>



Consultations de
la notice


Téléchargements du document