Back to search

Institutes outside Greece

Ανάλυση μέσης περίπτωσης αλγορίθμων ψαξίματος σε γράφους

Abstract

dc:description

We estimate the expected value of various search quantities for a variety of graph-searching methods, for example \dfs\ and \bfs. Our analysis applies to both directed and undirected random graphs, and it covers the range of interesting graph densities, including densities at which a random graph is disconnected with a giant connected component. We estimate the number of edges examined during the search, since this number is proportional to the running time of the algorithm. We find that for hardly connected graphs, all of the edges might be examined, but for denser graphs many fewer edges are generally required. We prove that any searching algorithm examines {$\Theta(n \log n)$} edges, if present, on all random graphs with {$n$} nodes but not necessarily on the complete graphs. One property of some searching algorithms is the maximum depth of the search. In \dfs, this depth can be used to estimate the space needed for the recursion stack. For random graphs of any density, even for disconnected graphs, we prove that this space is {$\Theta(n)$}. On the other hand, the depth of \bfs\ is {$\Theta(\log n / \!\log(p n))$}, where {$p$} is the probability of the existence of an edge. The size of the \dstr\ needed by any searching algorithm is proved to be {$\Theta(n)$}. If the search terminates at a particular node, any searching algorithm needs a \dstr\ of size {$\Theta(n)$}, and examines only {$\Theta(n)$} edges. Finally, we derive similar results for variants of the above searching algorithms, more general classes of searching algorithms, and for random graphs with multiple edges. These results are verified through simulations. The techniques employed to permit simulations of big graphs (few millions of nodes) and the results obtained are of general interest, especially to those performing similar experiments.

Degree

thesis:*
Grantor dc:publisher
Institutes outside Greece
Year dc:date
1990

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kapidakis, Sarantos
  • Καπιδάκης, Σαράντος

Subjects

dc:subject × 10

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/11944

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kapidakis, Sarantos; Καπιδάκης, Σαράντος. Ανάλυση μέσης περίπτωσης αλγορίθμων ψαξίματος σε γράφους. Institutes outside Greece, 1990. http://hdl.handle.net/10442/hedi/11944