New interface

Splitting a tournament into two subtournaments with given minimum outdegree

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)

Cited literature [14 references]

https://hal.inria.fr/hal-00943152
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

File

RR-8469.pdf
Files produced by the author(s)

Identifiers

• HAL Id : hal-00943152, version 1

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⟩

Record views