Karp's patching algorithm on dense digraph

Alan Frieze

We consider the following question. We are given a dense digraph $D$ with $n$ vertices and minimum in- and out-degree at least $\alpha n$, where $\alpha >1/2$ is a constant. The edges $E(D)$ o…