A Caltech Library Service

A dynamic graph algorithm for the highly dynamic network problem

Soedarmadji, Edwin and McEliece, Robert J. (2006) A dynamic graph algorithm for the highly dynamic network problem. In: Fourth annual IEEE International Conference on Pervasive Computing and Communications Workshops. IEEE , Los Alamitos, CA, pp. 101-105. ISBN 0-7695-2520-2 .

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


A recent flooding algorithm [1] guaranteed correctness for networks with dynamic edges and fixed nodes. The algorithm provided a partial answer to the highly dynamic network (HDN) problem, defined as the problem of devising a reliable message-passing algorithm over a HDN, which is a network – or a network mobility model – where edges and nodes can enter and leave the network almost arbitrarily. In this paper, we relax the flooding algorithms’ assumptions by removing the requirement that the network stays connected at all time, and extend the algorithm to solve the HDN problem where dynamic nodes are also involved. The extended algorithm is reliable: it guarantees message passing to all the destination nodes and terminates within a time bounded by a polynomial function of the maximum message transit time between adjacent nodes, and the maximum number of nodes in the network.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle
Additional Information:© 2006 IEEE. Issue Date: 13-17 March 2006. Date of Current Version: 27 March 2006.
Record Number:CaltechAUTHORS:20110616-134644787
Persistent URL:
Official Citation:Soedarmadji, E.; McEliece, R.J.; , "A dynamic graph algorithm for the highly dynamic network problem," Pervasive Computing and Communications Workshops, 2006. PerCom Workshops 2006. Fourth Annual IEEE International Conference on , vol., no., pp.5 pp.-105, 13-17 March 2006 doi: 10.1109/PERCOMW.2006.5 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24036
Deposited By: Tony Diaz
Deposited On:17 Jun 2011 17:26
Last Modified:03 Oct 2019 02:52

Repository Staff Only: item control page