Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45988
Title: A SIMPLE, EFFICIENT ALGORITHM FOR MAXIMUM FINDING ON RINGS
Authors: Higham, Lisa
Przytycka, Teresa
Keywords: Computer Science
Issue Date: 1-Dec-1992
Abstract: The maximum finding problem is: given a network of processors with distinct identifiers, find that processor with the maximum identifier. We present a new deterministic algorithm for maximum finding on asynchronous undirectional rings. To date the maximum finding algorithm with the best message complexity uses at most 1.356\fIn log n + O(n)\fR messages in the worst case. This algorithm is somewhat involved and its analysis is quite complicated. Our algorithm is simple, has a very much simpler analysis and achieves a lower worst case message complexity (less than 1.271\fIn log n + O(n)\fR messages). An additional contribution of this paper is a new perspective on this problem that exhibits its structure thus permitting a better understanding of various message saving mechanisms.
URI: http://hdl.handle.net/1880/45988
Appears in Collections:Higham, Lisa

Files in This Item:
File Description SizeFormat 
1992-494-32.pdf2.01 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.