Efficient Algorithms for Path Partitions

Report
Authors:Williams, Craig, Department of Computer ScienceUniversity of Virginia Richards, Dana, Department of Computer ScienceUniversity of Virginia
Abstract:

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

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Williams, Craig, and Dana Richards. "Efficient Algorithms for Path Partitions." University of Virginia Dept. of Computer Science Tech Report (1987).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1987