✦ LIBER ✦

Average Costs of a Graph Exploration: Upper and Lower Bounds

✍ Scribed by Nicola Galli

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 168 KB
Volume: 34
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1999.1053

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the exploration of random digraphs. We give upper and lower bounds for the expected number of edges traversed during an exploration. This result implies a lower bound for the expected running time of a wide class of algorithms, e.g., breadth-first-search, depth-first-search, and algorithms to determine a minimum spanning tree or to solve the single source shortest paths problem in a weighted digraph. Furthermore, we investigate the connectedness of nonhomogeneous random digraphs and we point out the relationship with the exploration algorithms.

📜 SIMILAR VOLUMES

Upper and lower bounds for the average-c

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

✍ Pippenger, Nicholas 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 1 views

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 ent

Lower-bounds on the connectivities of a

Lower-bounds on the connectivities of a graph

✍ Abdol H. Esfahanian 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 372 KB 👁 1 views

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 3 views

Lower bounds on the number of triangles

Lower bounds on the number of triangles in a graph

✍ David C. Fisher 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

Upper and lower bounds of 180° unit elem

Upper and lower bounds of 180° unit element of a ridge waveguide: Calculations and measurements

✍ George Goussetis; Djuradj Budimir; Joe Helszajn 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

## Abstract The upper and lower bounds on the actual solution of any microwave structure is of general interest. The purpose of this letter is to compare some calculations using the mode‐matching and finite‐element methods, with some measurements on a 180° ridge waveguide insert between standard WR

A class of self-complementary graphs and

A class of self-complementary graphs and lower bounds of some ramsey numbers

✍ C. R. J. Clapham 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 1 views

## Abstract A method is described of constructing a class of self‐complementary graphs, that includes a self‐complementary graph, containing no __K__~5~, with 41 vertices and a self‐complementary graph, containing no __K__~7~, with 113 vertices. The latter construction gives the improved Ramsey num