Finding good 2-partitions of digraphs I. Hereditary properties

Jørgen Bang-Jensen 1 Frédéric Havet 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Nous étudions la complexité de décider si un digraphe donné D admet une partition en deux sous-digraphes ayant des propriétés structurelles fixées. Dénotons par H et E les deux ensembles de propriétés de digraphes naturelles : H ={acyclique, complet, sans arcs, orienté, semicomplet, symétrique, tournoi} et E ={fortement connexe, connexe, degré sortant minimum au moins 1, degré entrant minimum au moins 1, semi-degré entrant minimum au moins 1, degré minimum au moins 1, avoir une arborescence sortante couvrante, avoir une arborescence entrante couvrante}. Dans ce rapport, nous déterminons la complexité de décider, pour toute paire d’entiers k1,k2, si un digraphie donné admet une partition en deux digraphes D1,D2 tels que |V(Di)|≥ki et Di a la propriété Pi pour i=1,2lorsque P1 ∈H et P2 ∈H∪E. Nous classifions également la complexité des mêmes problèmes restreints aux digraphies fortement connexes. La complexité des problèmes lorsque P1 et P2 sont toutes deux dans E est déterminée dans le rapport suivant (Rapport de Recherche INRIA RR-8868).
Type de document :
Rapport
[Research Report] RR-8867, INRIA Sophia Antipolis - I3S. 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01279332
Contributeur : Frederic Havet <>
Soumis le : jeudi 25 février 2016 - 20:12:34
Dernière modification le : lundi 4 décembre 2017 - 15:14:19
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 04:11:37

Fichier

RR-8867.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01279332, version 1

Collections

Citation

Jørgen Bang-Jensen, Frédéric Havet. Finding good 2-partitions of digraphs I. Hereditary properties. [Research Report] RR-8867, INRIA Sophia Antipolis - I3S. 2016. 〈hal-01279332〉

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

92