An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > journal & Dissertation > Item 987654321/29166

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/29166

Title:	An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs
Authors:	Hsieh,SY;Chen,GH;Ho,CW
Contributors:	資訊工程研究所
Keywords:	TREE
Date:	1998
Issue Date:	2010-06-29 20:15:19 (UTC+8)
Publisher:	中央大學
Abstract:	In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex distance-hereditary graph G, we show that the perfect dominating set problem on G can be solved in O(log(2) n) time using O(n + m) procesors on a CREW PRAM.
Relation:	ADVANCES IN COMPUTING SCIENCE-ASIAN' 98
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	617	View/Open

社群 sharing