Efficient Algorithms for Path PartitionsReport
An [a. b] path partition is a decomposition of the edges of a graph into a independent path sets and b matchings, where an independent path set is a set of paths that do not interesect each other. The path partition problem is related to other edge partition problems, such as edge coloring. It is shown that every graph with maximum degree 3 has a [2,0] path partition, and every graph with maximum degree 4 has a [2,1] path partition. Algorithmic proofs are given. The algorithms have linear-time sequential implementations and log - time parallel implementations.
Note: Abstract extracted from PDF file via OCR
All rights reserved (no additional license for public reuse)
Williams, Craig, and Dana Richards. "Efficient Algorithms for Path Partitions." University of Virginia Dept. of Computer Science Tech Report (1987).
University of Virginia, Department of Computer Science