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érenceDate
2018Titre du colloque
5th International Symposium on Combinatorial Optimization, ISCO 2018Date du colloque
2018-04Ville du colloque
MarrakeshPays du colloque
MoroccoTitre de l'ouvrage
Combinatorial OptimizationAuteurs 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
430Pages
115-120
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Cornaz, DenisLaboratoire 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 theoremPublications associées
Affichage des éléments liés par titre et auteur.
-
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
-
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2015) Communication / Conférence
-
Magnouche, Youcef (2017-06-26) Thèse
-
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha (2014) Communication / Conférence
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié