On disjoint directed cycles with prescribed minimum lengths - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

On disjoint directed cycles with prescribed minimum lengths

Résumé

In this paper, we show that the k-Linkage problem is polynomial-time solvable for digraphs with circumference at most 2. We also show that the directed cycles of length at least 3 have the Erdős-Pósa Property : for every n, there exists an integer t_n such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of t_n vertices that meets every directed cycle of length at least 3. From these two results, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F.
Fichier principal
Vignette du fichier
RR-8286.pdf (551.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00816135 , version 1 (19-04-2013)
hal-00816135 , version 2 (20-04-2013)

Identifiants

  • HAL Id : hal-00816135 , version 2

Citer

Frédéric Havet, Ana Karolinna Maia de Oliviera. On disjoint directed cycles with prescribed minimum lengths. [Research Report] RR-8286, INRIA. 2013. ⟨hal-00816135v2⟩
544 Consultations
241 Téléchargements

Partager

Gmail Facebook X LinkedIn More