ΖΗΤΗΜΑΤΑ ΣΥΝΕΚΤΙΚΟΤΗΤΑΣ ΣΕ ΤΥΧΑΙΟΥΣ ΓΡΑΦΟΥΣ

Περίληψη

ΜΕΛΕΤΑΜΕ ΠΡΟΒΛΗΜΑΤΑ ΣΥΝΕΚΤΙΚΟΤΗΤΑΣ (ΚΑΙ ΠΟΛΥΣΥΝΔΕΣΙΜΟΤΗΤΑΣ), ΕΠΕΚΤΑΣΗΣ, ΔΥΝΑΜΙΚΗΣ ΣΥΝΕΚΤΙΚΟΤΗΤΑΣ ΚΑΙ ΓΕΙΤΝΙΑΣΗΣ ΣΕ ΤΥΧΑΙΟΥΣ ΓΡΑΦΟΥΣ. ΠΙΟ ΣΥΓΚΕΚΡΙΜΕΝΑ, ΥΠΟΛΟΓΙΖΟΥΜΕ ΤΗΝ ΣΥΝΑΡΤΗΣΗ ΚΑΤΩΦΛΙΟΥ ΓΙΑ ΤΗΝ ΙΔΙΟΤΗΤΑ ΤΗΣ ΥΠΑΡΞΗΣ ΠΟΛΛΩΝ, ΣΥΝΤΟΜΩΝ, ΞΕΝΩΝ ΜΕΤΑΞΥ ΤΟΥΣ ΜΟΝΟΠΑΤΙΩΝ ΣΕ ΤΥΧΑΙΟΥΣ ΓΡΑΦΟΥΣ. ΕΠΙΣΗΣ, ΜΕΛΕΤΑΜΕ ΤΙΣΠΡΟΥΠΟΘΕΣΕΙΣ ΓΙΑ ΤΗΝ ΕΜΦΑΝΙΣΗ ΓΙΓΑΝΤΙΑΙΑΣ ΣΥΝΕΚΤΙΚΗΣ ΣΥΝΙΣΤΩΣΑΣ ΚΑΙ ΙΔΙΟΤΗΤΩΝ ΕΠΕΚΤΑΣΗΣ ΣΕ ΑΥΤΗΝ ΤΗ ΣΥΝΙΣΤΩΣΑ. ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΤΟΝ ΠΡΩΤΟ ΠΟΛΥΛΟΓΑΡΙΘΜΙΚΗΣ ΜΕΣΗΣ ΕΠΙΜΕΡΙΖΟΜΕΝΗΣ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ ΑΛΓΟΡΙΘΜΟ ΓΙΑ ΔΥΝΑΜΙΚΗ ΔΙΑΤΗΡΗΣΗ ΤΗΣ ΣΥΝΕΚΤΙΚΟΤΗΤΑΣ. ΤΕΛΟΣ, ΜΕΛΕΤΑΜΕ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΥΠΑΡΞΗΣ ΚΑΙ ΑΠΟΔΟΤΙΚΗΣ ΕΥΡΕΣΗΣ ΜΙΚΡΩΝ ΚΕΝΤΡΩΝ ΓΕΙΤΝΙΑΣΗΣ ΣΕ ΤΥΧΑΙΟΥΣ ΓΡΑΦΟΥΣ. ΤΑ ΠΑΡΑΠΑΝΩ ΑΠΟΤΕΛΕΣΜΑΤΑ ΕΧΟΥΝ ΣΗΜΑΝΤΙΚΕΣ ΕΦΑΡΜΟΓΕΣ ΣΤΗΝ ΑΝΑΛΥΣΗ ΚΑΙ ΤΟ ΣΧΕΔΙΑΣΜΟ ΑΞΙΟΠΙΣΤΩΝ ΚΑΙ ΑΠΟΔΟΤΙΚΩΝ ΔΙΚΤΥΩΝ ΥΠΟΛΟΓΙΣΤΩΝ.

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

WE STUDY CONNECTIVITY ISSUES IN RANDOM GRAPHS. WE ESTIMATE THE THRESHOLD FUNCTION FOR THE EXISTENCE OF MANY, SHORT, VERTEX DISJOINT PATHS IN RANDOM GRAPHS.FURTHERMORE, WE PROVE THE EXISTENCE OF A GIANT CONNECTED COMPONENT IN RANDOM GRAPHS WITH EDGE FAULTS. WE ALSO SHOW THAT THIS GIANT COMPONENT IS A CERTIFIABLE EFFICIENT EXPANDER WITH HIGH PROBABILITY. WE PRESENT THE FIRST DYNAMIC CONNECTIVITY ALGORITHM WITH POLYLOGARITHMIC EXPECTED (AMORTIZED) TIME. FINALLY,WE STUDY THE EXISTENCE AND EFFICIENT FINDING OF SMALL DOMINATING SETS IN RANDOM GRAPHS. A GREAT NUMBER OF APPLICATIONS IN RELIABLE NETWORK COMPUTING IS DISCUSSED.
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

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

DOI
10.12681/eadd/8638
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/8638
Εναλλακτικός τίτλος
CONNECTIVITY ISSUES IN RANDOM GRAPHS
Συγγραφέας
ΝΙΚΟΛΕΤΣΕΑΣ, ΣΩΤΗΡΗΣ
Ημερομηνία
1997
Ίδρυμα
Πανεπιστήμιο Πατρών. Σχολή Πολυτεχνική. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Εξεταστική επιτροπή
ΑΛΕΒΙΖΟΣ ΠΑΝΑΓΙΩΤΗΣ
ΑΛΕΞΙΟΥ ΓΙΩΡΓΟΣ
ΖΑΓΟΥΡΑΣ ΧΑΡΑΛΑΜΠΟΣ
ΚΑΒΒΑΔΙΑΣ ΔΗΜΗΤΡΗΣ
ΚΥΡΟΥΣΗΣ ΛΕΥΤΕΡΗΣ
ΣΠΥΡΑΚΗΣ ΠΑΥΛΟΣ
ΤΣΑΚΑΛΙΔΗΣ ΘΑΝΑΣΗΣ
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμες Ηλεκτρονικών Υπολογιστών & Πληροφορικής
Μηχανική & Τεχνολογία
Επιστήμες Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού & Μηχανικού Η/Υ
Λέξεις-κλειδιά
Αλγόριθμοι; ΑΝΑΛΥΣΗ ΜΕΣΗΣ ΤΙΜΗΣ; ΑΞΙΟΠΙΣΤΙΑ ΔΙΚΤΥΩΝ ΥΠΟΛΟΓΙΣΤΩΝ.; Δομές δεδομένων; ΔΥΝΑΜΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ; Θεωρία γράφων; ΣΥΝΕΚΤΙΚΟΤΗΤΑ ΓΡΑΦΩΝ; ΤΥΧΑΙΟΙ ΓΡΑΦΟΙ
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά