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 -