Polynomial Algorithms for Minimum Degree Partitions in Semicomplete Digraphs

Hanzhi Bai, Jin Yan

A 2-partition of a digraph is a partition of its vertex set into two nonempty parts. Degree-constrained 2-partition problems are generally computationally difficult, even when the…