Abstract
Let H be an undirected graph. A random graph of type—H is obtained by selecting edges of H independently and with probability p. We can thus represent a communication network H in which the links fail independently and with probability f=1−p. We study here two simple but fundamental types of H: The clique of n nodes (leading to the well known random graph G n,p ) and a random member of the set of all regular graphs of degree r (leading to a new type of random graphs, of the class G rn,p ).
Exact or asymptotic information about the remaining (with high probability) structure of type-H random graphs is of interest to applications in reliable network computing. In this work we concentrate on the question of existence of many short disjoint paths between all vertex pairs of G n,p . We also investigate the multiconnectivity properties of G rn,p . We show that:
-
1.
If p≥max(p 1, p 2), where p1=Ω(x/n−xl) and p 2=the x-connectivity threshold and l≥2 then G n,p has for vertex pairs u, v at least x disjoint paths of length at most 2l each, connecting u,v and this holds for all u, v with probability tending to 1 as n tends to infinity.
-
2.
G rn,p is r—connected except for O(1) vertices w.h.p. for all failure probabilities f=1-p≤n-ε (ε > 0 fixed).
-
3.
G rn,p is highly disconnected a.c. for constant f and any r<1/2√log n, but is r-connected w.h.p. when r≥α log n, α ≥2.
-
4.
Even when G rn,p is disconnected, it still has a giant connected component of small diameter even when r=O(1). An O(n log n) time algorithm is given to construct the giant component.
Many network applications are discussed, including PRAM simulations, gossiping and multitasking in distributed memory parallel machines.
This research was partially supported by the NSF grant CCR-89-6949 and by the EEC ESPRIT Basic Research Projects ALCOM II and GEPPCOM.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Angluin and L. Valiant, “Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings”, JCSS, vol. 18, pp. 155–193, 1979.
B. Bollobas, “Random Graphs”, Academic Press, 1985.
B. Bollobas and A. G. Thomason, “Random Graphs of small order”, Random Graphs, Annals of Discr. Math., pp. 47–97, 1985.
S. Even and R. E. Tarjan, “Network flow and testing graph connectivity”, SLAM J. Comput., vol. 4, pp. 507–518, 1975.
J. Hastad, T. Leighton and M. Newman, “Fast Computation Using Faulty Hypercubes”, Proc. 21st ACM Symp. on Theory of Computing, pp. 251–263, 1989.
S. Janson, D. Knuth, T. Luczak, B. Pittel, “The birth of the giant component”, Random Structures and Algorithms, vol.4, pp. 232–355, 1993.
Z. Kedem, K. Palem, and P. Spirakis, “Efficient Robust Parallel Computations”, Proc. 22nd ACM Symp. on Theory of Computing, pp. 138–148, 1990.
Z. Kedem, K. Palem, A. Raghunathan and P. Spirakis, “Combining Tentative and Definite Executions for Very Fast Dependable Parallel Computing”, Proc. 23nd ACM Symp. on Theory of Computing, 1991.
Z. Kedem, K. Palem, P. Spirakis and M. Yung, “Faulty Random Graphs: reliable efficient-on-the-average network computing”, Computer Technology Institute (Patras, Greece) Technical Report, 1993.
D. Peleg and E. Upfal, “Constructing Disjoint Paths on Expander Graphs”, Proc. 19th ACM Symp. on Theory of Computing, pp. 264–273, 1987.
M. Rabin, “Efficient Dispersal of Information for Security, Load Balancing and Fault Tolerance”, JACM, vol. 36, no. 2, pp. 335–348, 1989.
J. Spencer, “Ten Lectures on the Probabilistic Method”, SIAM, 1987.
L. Valiant, “The complexity of enumeration and reliability problems”, SIAM J. Comp., vol. 8, pp. 410–421, 1979.
L. Valiant, “A Bridging Model for Parallel Computation”, CACM, vol. 33, no. 8, pp. 103–111, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nikoletseas, S., Palem, K., Spirakis, P., Yung, M. (1994). Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing. In: Abiteboul, S., Shamir, E. (eds) Automata, Languages and Programming. ICALP 1994. Lecture Notes in Computer Science, vol 820. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58201-0_94
Download citation
DOI: https://doi.org/10.1007/3-540-58201-0_94
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58201-4
Online ISBN: 978-3-540-48566-7
eBook Packages: Springer Book Archive