13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing
A Time-Optimal Solution for the Path Cover Problem on Cographs
San Juan, Puerto Rico
April 12-April 16
ISBN: 0-7695-0143-5
We show that the notoriously difficult problem of finding and reporting the smallest number of vertex-disjoint paths that cover the vertices of a graph can be solved time-and work-optimally for cographs. Our algorithm solves this problem in O(log n) time using n log n processors on the EREW-PRAM for an n-vertex cograph G represented by its cotree.
Citation:
K. Nakano, S. Olariu, A.Y. Zomaya, "A Time-Optimal Solution for the Path Cover Problem on Cographs," ipps, pp.26, 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, 1999
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||