Splitting a tournament into two subtournaments with given minimum outdegree
Résumé
A {\it $(k_1,k_2)$-outdegree-splitting} of a digraph $D$ is a partition $(V_1,V_2)$ of its vertex set such that $D[V_1]$ and $D[V_2]$ have minimum outdegree at least $k_1$ and $k_2$, respectively. We show that there exists a minimum function $f_T$ such that every tournament of minimum outdegree at least $f_T(k_1,k_2)$ has a $(k_1,k_2)$-outdegree-splitting, and $f_T(k_1,k_2) \leq k_1^2/2+3k_1/2 +k_2+1$. We also show a polynomial-time algorithm that finds a $(k_1,k_2)$-outdegree-splitting of a tournament if one exists, and returns 'no' otherwise. We give better bound on $f_T$ and faster algorithms when $k_1=1$.
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$.
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...