Item Details

Efficient Algorithms for Path Partitions

Williams, Craig; Richards, Dana
Format
Report
Author
Williams, Craig
Richards, Dana
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
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1987
Published Date
1987
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online