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

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

0.00 Avg rating—0 Votes
Article ID: iaor1995279
Country: Netherlands
Volume: 42
Issue: 2/3
Start Page Number: 291
End Page Number: 303
Publication Date: Apr 1993
Journal: Discrete Applied Mathematics
Authors:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.