A Time-Optimal Solution for the Path Cover Problem on Cographs

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by K. Nakano Articles by S. Olariu Articles by A.Y. Zomaya

13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing

San Juan, Puerto Rico

April 12-April 16

ISBN: 0-7695-0143-5

	ASCII Text	x
	K. Nakano, S. Olariu, A.Y. Zomaya, "A Time-Optimal Solution for the Path Cover Problem on Cographs," Parallel Processing Symposium, International, pp. 26, 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, 1999.

	BibTex	x
	@article{ 10.1109/IPPS.1999.760430, author = {K. Nakano and S. Olariu and A.Y. Zomaya}, title = {A Time-Optimal Solution for the Path Cover Problem on Cographs}, journal ={Parallel Processing Symposium, International}, volume = {0}, year = {1999}, issn = {1063-7133}, pages = {26}, doi = {http://doi.ieeecomputersociety.org/10.1109/IPPS.1999.760430}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Processing Symposium, International TI - A Time-Optimal Solution for the Path Cover Problem on Cographs SN - 1063-7133 SP EP A1 - K. Nakano, A1 - S. Olariu, A1 - A.Y. Zomaya, PY - 1999 VL - 0 JA - Parallel Processing Symposium, International ER -

K. Nakano

S. Olariu

A.Y. Zomaya

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPPS.1999.760430

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.