DocumentCode
2746942
Title
A time-optimal solution for the path cover problem on cographs
Author
Nakano, Kaoru ; Olariu, Stephan ; Zomaya, A.Y.
Author_Institution
Dept. of Electr. & Comput. Eng., Nagoya Inst. of Technol., Japan
fYear
1999
fDate
12-16 Apr 1999
Firstpage
26
Lastpage
30
Abstract
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
Keywords
computational geometry; graph theory; EREW-PRAM; cographs; cotree; n-vertex cograph; path cover problem; time-optimal solution; vertex-disjoint paths; Australia Council; Computer science; Parallel algorithms;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Processing, 1999. 13th International and 10th Symposium on Parallel and Distributed Processing, 1999. 1999 IPPS/SPDP. Proceedings
Conference_Location
San Juan
Print_ISBN
0-7695-0143-5
Type
conf
DOI
10.1109/IPPS.1999.760430
Filename
760430
Link To Document