Finding good 2-partitions of digraphs II. Enumerable properties

Résumé : Nous poursuivons l’étude, commencée dans le rapport de recherche INRIA RR-8867, de la complexité de décider si un digraphe donné D admet une partition en deux sous-digraphes ayant des propriétés struc- turelles fixées et des tailles minimum données. Soit E l’ensemble des propriétés de digraphes : E ={fortement connexe, connexe, degré sort ant 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, pour tout choix P1,P2 de E et toute paire d’entiers naturels k1,k2, la complexité de décider si un digraphe admet une partition en deux digraphes D1 , D2 telle que Di a la propriété Pi et |V (Di )| ≥ ki , i = 1, 2. Nous classifions également la complexité des mêmes prob- lèmes restreints aux digraphes fortement connexes. Les complexités des problèmes analogues pour P1 ∈ H et P2 ∈ H ∪ E, avec H ={acyclique, complet, sans arcs, orienté, semicomplet, symétrique, tournoi} ont été établies dans le rapport de recherche INRIA RR-8867.
Type de document :
Rapport
[Research Report] RR-8868, INRIA Sophia Antipolis - I3S. 2016


https://hal.inria.fr/hal-01279338
Contributeur : Frederic Havet <>
Soumis le : jeudi 25 février 2016 - 20:26:41
Dernière modification le : samedi 18 février 2017 - 01:20:41
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 04:01:07

Fichier

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

Identifiants

  • HAL Id : hal-01279338, version 1

Relations

Citation

Jørgen Bang-Jensen, Nathann Cohen, Frédéric Havet. Finding good 2-partitions of digraphs II. Enumerable properties. [Research Report] RR-8868, INRIA Sophia Antipolis - I3S. 2016. <hal-01279338>

Partager

Métriques

Consultations de
la notice

114

Téléchargements du document

66