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

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$.
Document type :
Reports
Domain :

Cited literature [8 references]

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⟩

Record views