Computing Vertex-Disjoint Paths using MAOs

Johanna E. Preißer, Jens M. Schmidt

Let G be a graph with minimum degree $\delta$. It is well-known that maximal adjacency orderings (MAOs) compute a vertex set S such that every pair of S is connected by at least $\delta$ int…