LCS Publication Details
Publication Title: LINEAR TIME ALGORITHM FOR MINIMUM NETWORK PARTITION
Publication Author: Awerbuch, Baruch
Additional Authors:
LCS Document Number: MIT-LCS-TM-350
Publication Date: 3-1-1988
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
This paper develops linear time distributed algorithms for the problem of Minimum Network Partition (MNP) in a point-to -point synchronous distributed network. The problem can be stated as follows. We are given distinct positive weights on every edge of an undirected graph G(V,E), and a parameter H. The MNP partition with parameter H, or, short, an H-partition, is spanning forest of the graph G(V,E) and contains at least H nodes. Previous solutions to this problem required O (E+Vlog) messages and O(V) time [A-87]. Our solution requires O(E+VlogV) messages and O(H) time.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.