The average performance of a parallel stable marriage algorithm

ASIAIR > College of Computer Science > Department of Applied Informatics and Multimedia > Journal Article > Item 310904400/4668

Please use this identifier to cite or link to this item: http://asiair.asia.edu.tw/ir/handle/310904400/4668

Title:	The average performance of a parallel stable marriage algorithm
Authors:	S. S. Tseng
Contributors:	Department of Information Science and Applications
Date:	1989
Issue Date:	2009-11-30 08:03:01 (UTC+0)
Publisher:	Asia University
Abstract:	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)).
Relation:	BIT Numerical Mathematics 29(3):488-456
Appears in Collections:	[Department of Applied Informatics and Multimedia] Journal Article

Files in This Item:

File	Description	Size	Format
		0Kb	Unknown	664	View/Open
310904400-4668.doc		36Kb	Microsoft Word	413	View/Open