Thumbnail - Request a copy

The Minimum Rooted-Cycle Cover Problem

Cornaz, Denis; Magnouche, Youcef (2018), The Minimum Rooted-Cycle Cover Problem, in 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
Conference title
5th International Symposium on Combinatorial Optimization, ISCO 2018
Conference date
2018-04
Conference city
Marrakesh
Conference country
Morocco
Book title
Combinatorial Optimization
Book author
Lee, Jon; Rinaldi, Giovanni; Mahjoub, A. Ridha
Publisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-319-96150-7
Number of pages
430
Pages
115-120
Publication identifier
Metadata
Show full item record
Author(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]
Abstract (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.
Subjects / Keywords
Kőnig’s theorem; Menger’s theorem