𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Upper and lower bounds for the average-case complexity of path-search

✍ Scribed by Pippenger, Nicholas

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
125 KB
Volume
33
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting entirely of idle vertices or to find a cut (separating the given input from the given output) consisting entirely of busy vertices. We shall also allow the search to fail to find either a path or a cut with some probability bounded by a parameter called the failure probability. This is to be accomplished by sequentially probing the idle-or-busy status of vertices, where the vertex chosen for each probe may depend on the outcome of previous probes. Thus, a search algorithm may be modeled as a decision tree. For average-case analysis, we assume that each vertex is independently idle with some fixed probability, called the vacancy probability (and therefore busy with the complementary probability). For one commonly studied channel graph type, the parallel graph, we show that the expected number of probes is at most proportional to the length of a path, irrespective of the vacancy probability, and even if the allowed failure probability is zero. Another type of channel graph that we study is the spider-web graph, which is superior to the parallel graph as regards linking probability (the probability that an idle path, rather than a busy cut, exists). For this graph, we give upper and lower bounds that grow exponentially with the length of a path, when the vacancy probability and failure probability are fixed appropriately.

📜 SIMILAR VOLUMES

Accurate lower and upper bounds of the e
Accurate lower and upper bounds of the energy spectrum for the asymmetrical two-well potentials
✍ H. Taşeli 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB 👁 1 views

Trigonometric basis sets are used in a Rayleigh-Ritz variational method for computing two-sided eigenvalue bounds of the Schrodinger equation in one dimension. The method is based on truncating the infinite interval and solving an eigenvalue problem which obeys the von Neumann and the Dirichlet boun

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
✍ Luc Devroye; Carlos Zamora-Cura 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co

Upper- and lower-bound Hylleraas–CI calc
Upper- and lower-bound Hylleraas–CI calculations for the nonrelativistic Po states of the 4He isotope
✍ Ralf Hilger; Hans-Peter Merckens; Arne Lüchow; Heinz Kleindienst 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 1 views

Extensive Hylleraas᎐CI calculations for the lowest P o states of 4 He were performed. The dependence of the variational energy values E on the mass parameter given by s m 2qrm y is discussed. Furthermore, lower bounds to E were calculated He e using variance minimization.