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

Περίληψη

Υπολογίζουμε την προσδοκόμενη τιμή διαφόρων ποσοτήτων για μια ποικιλία από μεθόδους ψαξίματος σε γράφους, όπως στο depth-first search και στο breadth-first search. Η ανάλυσή μας εφαρμόζεται σε κατευθυνόμενους και μη κατευθυνόμενους τυχαίους γράφους και καλύπτει την περιοχή των ενδιαφέρουσων πυκνοτήτων των γράφων, περιλαμβάνοντας πυκνότητες στις οποίες ο τυχαίος γράφος αποτελείται από περισσότερες από μία συνιστώσες και έχει μία γιγαντιαία συνιστώσα. Υπολογίζουμε τον αριθμό ακμών που εξετάζεται κατά τη διάρκεια του ψαξίματος, καθώς αυτός ο αριθμός είναι ανάλογος με το χρόνο τρεξίματος του αλγορίθμου. Βρίσκουμε πως για γράφους που μόλις είναι ενωμένοι, μπορεί να εξετάσουμε όλες τις ακμές, αλλά για πυκνότερους γράφους γενικά χρειάζονται πολύ λιγότερες ακμές. Αποδεικνύουμε πως οποιοσδήποτε αλγόριθμος ψαξίματος εξετάζει Θ(n logn) ακμές, εφόσον υπάρχουν, σε όλους τους τυχαίους γράφους με n κόμβους, αλλά όχι απαραίτητα και στους πλήρεις γράφους. Μία ιδιότητα μερικών αλγορίθμων ψαξίματος ...
περισσότερα

Περίληψη σε άλλη γλώσσα

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 di ...
περισσότερα
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/11944
Εναλλακτικός τίτλος
Average-case analysis of graph-searching algorithms
Συγγραφέας
Καπιδάκης, Σαράντος
Ημερομηνία
1990
Ίδρυμα
Princeton University. Department of Computer Science
Εξεταστική επιτροπή
Sedgewick Robert
Λέξεις-κλειδιά
Γράφοι; Αλγόριθμοι; Αλγόριθμοι ψαξίματος; Θ (n) ακμές; Θ (n logn) ακμές
Χώρα
Η.Π.Α.
Γλώσσα
Ελληνικά
Άλλα στοιχεία
154 σελ., εικ.