Thumbnail - Request a copy

The Minimum Rooted-Cycle Cover Problem

Cornaz, Denis; Magnouche, Youcef (2018), The Minimum Rooted-Cycle Cover Problem, dans Lee, Jon; Rinaldi, Giovanni; Mahjoub, A. Ridha, Combinatorial Optimization, Springer International Publishing : Berlin Heidelberg, p. 115-120. 10.1007/978-3-319-96151-4_10

Type
Communication / Conférence
Date
2018
Titre du colloque
5th International Symposium on Combinatorial Optimization, ISCO 2018
Date du colloque
2018-04
Ville du colloque
Marrakesh
Pays du colloque
Morocco
Titre de l'ouvrage
Combinatorial Optimization
Auteurs de l’ouvrage
Lee, Jon; Rinaldi, Giovanni; Mahjoub, A. Ridha
Éditeur
Springer International Publishing
Ville d’édition
Berlin Heidelberg
Isbn
978-3-319-96150-7
Nombre de pages
430
Pages
115-120
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Cornaz, Denis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Magnouche, Youcef
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
Given an undirected rooted graph, a cycle containing the root vertex is called a rooted cycle. We study the combinatorial duality between vertex-covers of rooted-cycles, which generalize classical vertex-covers, and packing of disjoint rooted cycles, where two rooted cycles are vertex-disjoint if their only common vertex is the root node. We use Menger’s theorem to provide a characterization of all rooted graphs such that the maximum number of vertex-disjoint rooted cycles equals the minimum size of a subset of non-root vertices intersecting all rooted cycles, for all subgraphs.
Mots-clés
Kőnig’s theorem; Menger’s theorem