The average performance of a parallel stable marriage algorithm

ASIA unversity > 資訊學院 > 行動商務與多媒體應用學系 > 會議論文 > Item 310904400/7196

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://asiair.asia.edu.tw/ir/handle/310904400/7196

题名:	The average performance of a parallel stable marriage algorithm
作者:	S. S. Tseng
贡献者:	Department of Computer Science and Information Engineering
日期:	1986
上传时间:	2010-01-29 05:42:18 (UTC+0)
出版者:	Asia University
摘要:	In this paper, Tseng and Lee's parallel algorithm to solve the stable marriage prolem is analyzed. It is shown that the average number of parallel proposals of the algorithm is of ordern by usingn processors on a CREW PRAM, where each parallel proposal requiresO(loglog(n) time on CREW PRAM by applying the parallel selection algorithms of Valiant or Shiloach and Vishkin. Therefore, our parallel algorithm requiresO(nloglog(n)) time. The speed-up achieved is log(n)/loglog(n) since the average number of proposals required by applying McVitie and Wilson's algorithm to solve the stable marriage problem isO(nlog(n)).
關聯:	Proceeding of 1986 MIST Workshop, Hsinchu, Taiwan, R.O.C.:469-473
显示于类别:	[行動商務與多媒體應用學系] 會議論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	467	检视/开启

在ASIAIR中所有的数据项都受到原著作权保护.