Show simple item record

The Minimum Rooted-Cycle Cover Problem

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorCornaz, Denis
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMagnouche, Youcef
dc.date.accessioned2019-07-17T10:08:57Z
dc.date.available2019-07-17T10:08:57Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19248
dc.descriptionLecture Notes in Computer Science book series (LNCS, volume 10856)en
dc.language.isoenen
dc.subjectKőnig’s theoremen
dc.subjectMenger’s theoremen
dc.subject.ddc003en
dc.titleThe Minimum Rooted-Cycle Cover Problemen
dc.typeCommunication / Conférence
dc.description.abstractenGiven 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.citationpages115-120en
dc.relation.ispartoftitleCombinatorial Optimizationen
dc.relation.ispartofeditorLee, Jon
dc.relation.ispartofeditorRinaldi, Giovanni
dc.relation.ispartofeditorMahjoub, A. Ridha
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2018
dc.relation.ispartofpages430en
dc.relation.ispartofurl10.1007/978-3-319-96151-4en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-96150-7en
dc.relation.conftitle5th International Symposium on Combinatorial Optimization, ISCO 2018en
dc.relation.confdate2018-04
dc.relation.confcityMarrakeshen
dc.relation.confcountryMoroccoen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-96151-4_10en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-07-17T10:02:49Z
hal.identifierhal-02186399*
hal.version1*
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record