Herbert Edelsbrunner, Mark H. Overmars, et al.
International Journal of Computer Mathematics
Paper
On Greene-Kleitman's theorem for general digraphs
Abstract
Linial conjectured that Greene-Kleitman's theorem can be extended to general digraphs. We prove a stronger conjecture of Berge for digraphs having k-optimal path partitions consisting of 'long' paths. The same method yields known results for acyclic digraphs, and extensions of various theorems of Greene and Frank to acyclic digraphs. © 1993.