hal.structure.identifier | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE] | |
dc.contributor.author | Cornaz, Denis | |
hal.structure.identifier | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE] | |
dc.contributor.author | Magnouche, Youcef | |
dc.date.accessioned | 2019-07-17T10:08:57Z | |
dc.date.available | 2019-07-17T10:08:57Z | |
dc.date.issued | 2018 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/19248 | |
dc.description | Lecture Notes in Computer Science book series (LNCS, volume 10856) | en |
dc.language.iso | en | en |
dc.subject | Kőnig’s theorem | en |
dc.subject | Menger’s theorem | en |
dc.subject.ddc | 003 | en |
dc.title | The Minimum Rooted-Cycle Cover Problem | en |
dc.type | Communication / Conférence | |
dc.description.abstracten | 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. | en |
dc.identifier.citationpages | 115-120 | en |
dc.relation.ispartoftitle | Combinatorial Optimization | en |
dc.relation.ispartofeditor | Lee, Jon | |
dc.relation.ispartofeditor | Rinaldi, Giovanni | |
dc.relation.ispartofeditor | Mahjoub, A. Ridha | |
dc.relation.ispartofpublname | Springer International Publishing | en |
dc.relation.ispartofpublcity | Berlin Heidelberg | en |
dc.relation.ispartofdate | 2018 | |
dc.relation.ispartofpages | 430 | en |
dc.relation.ispartofurl | 10.1007/978-3-319-96151-4 | en |
dc.subject.ddclabel | Recherche opérationnelle | en |
dc.relation.ispartofisbn | 978-3-319-96150-7 | en |
dc.relation.conftitle | 5th International Symposium on Combinatorial Optimization, ISCO 2018 | en |
dc.relation.confdate | 2018-04 | |
dc.relation.confcity | Marrakesh | en |
dc.relation.confcountry | Morocco | en |
dc.relation.forthcoming | non | en |
dc.identifier.doi | 10.1007/978-3-319-96151-4_10 | en |
dc.description.ssrncandidate | non | en |
dc.description.halcandidate | oui | en |
dc.description.readership | recherche | en |
dc.description.audience | International | en |
dc.relation.Isversionofjnlpeerreviewed | non | en |
dc.relation.Isversionofjnlpeerreviewed | non | en |
dc.date.updated | 2019-07-17T10:02:49Z | |
hal.identifier | hal-02186399 | * |
hal.version | 1 | * |
hal.author.function | aut | |
hal.author.function | aut | |