About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica
Paper
Dynamic detection of subgraphs in computer networks
Abstract
Most distributed algorithms for computer networks are designed to work with arbitrary graph structures. Most networks, however, can usually be decomposed into subgraphs with a specific structure. Detecting and exploiting these subgraphs can considerably reduce the storage and communication cost of the algorithm. In this paper we propose a distributed algorithm for detecting and exploiting tree subgraphs. In a network with fixed topology, the algorithm is optimal in terms of communication complexity. The algorithm also dynamically adapts to changes in network topology caused by link failure and recovery. The dynamic operation of the algorithm is incremental as only nodes that may be affected by the change reinitiate the algorithm. Another important property of our algorithm is that it requires no node identities or sequence numbers. We examine how this idea can be extended to other subgraph structures. © 1990 Springer-Verlag New York Inc.