Optimal determination of sourcedestination connectivity in random graphs
Conference Paper

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

© 2015 ACM. This paper investigates the problem of optimally determining sourcedestination connectivity in random graphs. We consider the classic ErdosRenyi (ER) random graph with n nodes, where an edge independently exists between any two nodes with probability p. The problem examined is that of determining whether a given pair of nodes, a source S and a destination D, are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest SD path as well as in a minimum SD cut. Among such edges, it chooses that which leads to the most opportunities for connection. Interestingly, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n=n. The policy is efficiently implementable, requiring no more than 30log2 n operations to determine which edge to test next. The result also extends to some more general graphs.
name of conference

the 15th ACM international symposium
published proceedings

Proceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing  MobiHoc '14
author list (cited authors)

Fu, L., Wang, X., & Kumar, P. R
citation count
complete list of authors

Fu, LuoyiWang, XinbingKumar, PR
publication date
publisher
Identity
Digital Object Identifier (DOI)
International Standard Book Number (ISBN) 13
Additional Document Info
start page
end page
volume