Browse Prior Art Database

ON THE DEPTH OF A RANDOM GRAPH

IP.com Disclosure Number: IPCOM000128236D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 14 page(s) / 29K

Publishing Venue

Software Patent Institute

Related People

John H. Reif: AUTHOR [+4]

Abstract

This paper investigates the probability distribution of the depth of a random graph Gn,p, or a random digraph Dn,p, We show the average depth of a random graph or digraph to be 0(log n), for all (but a small range) of values of p. We furthermore show that the probability that the depth is 0(log n) tends to 1 as n tends to infinity for all (but a small. range) of values of p. We also prove that for [Equation ommitted] the depth d of [Equation ommitted] is less than or equal to 3 with probability tending to 1 as n tends to -. Although the result that the average depth of [Equation ommitted] can be deduced from results of Erdos and Renyi for several values of p; the result for sparse graphs [Equation ommitted] and the result for very dense graphs [Equation ommitted] are new contributions. The above results are useful in studies of the expected performance of parallel graph algorithms.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 25% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON THE DEPTH OF A RANDOM GRAPH

by

John H. Reif* and Paul Spirakis

y . ;_ July 1983 y'-..

f,. 'Technical Report No. 82 _. _ - w

*Aiken Computation Laboratory, Harvard University.

This work was supported in part by the National Science Foundation Grant NSF-MCS 8300630.

SUMMARY

This paper investigates the probability distribution of the depth of a random graph Gn,p, or a random digraph Dn,p, We show the average depth of a random graph or digraph to be 0(log n), for all (but a small range) of values of p. We furthermore show that the probability that the depth is 0(log n) tends to 1 as n tends to infinity for all (but a small. range) of values of p. We also prove that for

(Equation Omitted)

the depth d of

(Equation Omitted)

is less than or equal to 3 with probability tending to 1 as n tends to -. Although the result that the average depth of

(Equation Omitted)

can be deduced from results of Erdos and Renyi for several values of p; the result for sparse graphs

(Equation Omitted)

and the result for very dense graphs

(Equation Omitted)

are new contributions. The above results are useful in studies of the expected performance of parallel graph algorithms.

1. INTRODUCTION

New York University Page 1 Dec 31, 1982

Page 2 of 14

ON THE DEPTH OF A RANDOM GRAPH

DEFINITION: Let

(Equation Omitted)

be a (directed or undirected) graph and let

(Equation Omitted)

be the length of the shortest path from v to w if any, - ~ otherwise. Then the depth, d(G), of the graph G is defined

to be the

(Equation Omitted)

Note that for undirected graphs

(Equation Omitted)

with nontrivial connected components, d(G) is the maximum of the diameters of the connected components of G.

The random graph

(Equation Omitted)

i:s defined here as in [Erdos, Renyi, 60] and the random digraph Dn,p as in [Angluin, Valiant,
79].

DEFINITION: For

(Equation Omitted)

be a random variable whose values are graphs (digraphs) on the vertex set

(Equation Omitted)

then

(Equation Omitted)

and these probabilities are independent for different e. Note that we refer here to simple linear graphs.

In the paper we investigate the probability distribution of the depth of a random graph Gn,,p or a random digraph Dn,p. The mean value d (and bounds on the probability distribution) of the depth are stated. We prove the following theorems: THEOREM 1.1: There is a constant

(Equation Omitted)

New York University Page 2 Dec 31, 1982

Page 3 of 14

ON THE DEPTH OF A RANDOM GRAPH

such that for an

(Equation Omitted)

probability p in the ran

(Equation Omitted)

the graph Gprobability has average depth

(Equation Omitted)

Furthermore,

(Equation Omitted)

tends to

1 as n tends to ~.

THEOREM 1.2: There _is _a constant

(Equation Omitted)

.such that for an c probability p in the range

(Equation Omitted)

, the digraph D n ,P has average depth

(Equation Omitted)

Furthermore,

(Equation Omitted)

tends to 1 as n tends to ~.

We also prove that for p a c (c a partic...