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

Julien Bensmail 1 Valentin Garnero 1 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 : By Berge's theorem, finding a maximum matching in a graph relies on the use of augmenting paths. When no further constraint is added, Edmonds' algorithm allows to compute a maximum matching in polynomial time by sequentially augmenting such paths. Motivated by applications in the scheduling of airline operations, we consider a similar problem where only paths of bounded length can be augmented. Precisely, let k ≥ 1 be an odd integer, a graph G and a matching M 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? We first prove that this problem can be solved in polynomial time for k ≤ 3 in any graph and that it is NP-complete for any fixed k ≥ 5 in the class of planar bipartite graphs of degree at most 3 and arbitrarily large girth. We then prove that this problem is in P, for any k, in several subclasses of trees such as caterpillars or trees with all vertices of degree at least 3 " far appart ". Moreover, this problem can be solved in time O(n) in the class of n-node trees when k and the maximum degree are fixed parameters. Finally, we consider a more constrained problem where only paths of length exactly k can be augmented. We prove that this latter problem becomes NP-complete for any fixed k ≥ 3 and in trees when k is part of the input.
Type de document :
Communication dans un congrès
IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), Sep 2017, Marseille, France. 2017, IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS)
Liste complète des métadonnées


https://hal.inria.fr/hal-01534598
Contributeur : Nicolas Nisse <>
Soumis le : mercredi 7 juin 2017 - 18:29:20
Dernière modification le : jeudi 15 juin 2017 - 09:09:33

Fichier

LAGOS17.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01534598, version 1

Collections

Citation

Julien Bensmail, Valentin Garnero, Nicolas Nisse, Alexandre Salch, Valentin Weber. Recovery of disrupted airline operations using k-Maximum Matching in graphs. IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), Sep 2017, Marseille, France. 2017, IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS). <hal-01534598>

Partager

Métriques

Consultations de
la notice

56

Téléchargements du document

19