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 , Laboratoire I3S - 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$.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01116487
Contributor : Nicolas Nisse <>
Submitted on : Tuesday, February 17, 2015 - 5:59:15 PM
Last modification on : Thursday, January 3, 2019 - 2:46:03 PM
Long-term archiving on : Tuesday, May 26, 2015 - 11:25:35 AM

File

RR-8679.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01116487, version 1

Citation

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⟩

Share

Metrics

Record views

535

Files downloads

300