TY - JOUR

T1 - A fast randomized algorithm for partitioning a graph into paths of fixed length

AU - Stougie, L.

N1 - 0768.68183

PY - 1993

Y1 - 1993

N2 - A randomized extension-rotation algorithm is presented to partition an undirected graph G=(V,E) into vertex disjoint paths of fixed length. In O(|V|log|V|) time it finds such a partition if one exists with high probability, when applied to random graphs with sufficiently high edge density

AB - A randomized extension-rotation algorithm is presented to partition an undirected graph G=(V,E) into vertex disjoint paths of fixed length. In O(|V|log|V|) time it finds such a partition if one exists with high probability, when applied to random graphs with sufficiently high edge density

U2 - 10.1016/0166-218X(93)90052-P

DO - 10.1016/0166-218X(93)90052-P

M3 - Article

VL - 42

SP - 291

EP - 303

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 2-3

ER -