Splitting a tournament into two subtournaments with given minimum outdegree

Frédéric Havet 1 Bernard Lidicky 2
1 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é : Un {\it $(k_1,k_2)$-partage} d'un digraphe $D$ est une partition $(V_1,V_2)$ de son ensemble de sommets telle que $D[V_1]$ et $D[V_2]$ soient de degréß sortant minimum au moins $k_1$ et $k_2$, respectivement. Nous établissons l'existence d'une fonction (minimum) $f_T$ telle que tout tournoi de degré sortant minimum au moins $f_T(k_1,k_2)$ a un $(k_1,k_2)$-partage, et que $f_T(k_1,k_2) \leq k_1^2/2+3k_1/2 +k_2+1$. Nous donnons également un algorithme en temps polynomial qui trouve un $(k_1,k_2)$-partage d'un tournoi s'il en existe un et renvoie 'non' sinon. Nous donnons de meilleures bornes sur $f_T$ et des algorithmes plus rapides pour $k_1=1$.
Type de document :
Rapport
[Research Report] RR-8469, INRIA. 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-00943152
Contributeur : Frederic Havet <>
Soumis le : vendredi 7 février 2014 - 09:53:34
Dernière modification le : samedi 17 septembre 2016 - 01:36:34
Document(s) archivé(s) le : lundi 12 mai 2014 - 11:51:27

Fichier

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

Identifiants

  • HAL Id : hal-00943152, version 1

Collections

Citation

Frédéric Havet, Bernard Lidicky. Splitting a tournament into two subtournaments with given minimum outdegree. [Research Report] RR-8469, INRIA. 2014. <hal-00943152>

Partager

Métriques

Consultations de
la notice

245

Téléchargements du document

125