Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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$.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Friday, February 7, 2014 - 9:53:34 AM
Last modification on : Friday, November 18, 2022 - 9:26:31 AM
Long-term archiving on: : Monday, May 12, 2014 - 11:51:27 AM


Files produced by the author(s)


  • HAL Id : hal-00943152, version 1


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



Record views


Files downloads