Abstract
dc:descriptionWE 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.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 1997
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Νικολετσέας, Σωτήρης
Subjects
dc:subject × 24- Αλγόριθμοι
- ΑΝΑΛΥΣΗ ΜΕΣΗΣ ΤΙΜΗΣ
- ΑΞΙΟΠΙΣΤΙΑ ΔΙΚΤΥΩΝ ΥΠΟΛΟΓΙΣΤΩΝ.
- Δομές δεδομένων
- ΔΥΝΑΜΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ
- Θεωρία γράφων
- ΣΥΝΕΚΤΙΚΟΤΗΤΑ ΓΡΑΦΩΝ
- ΤΥΧΑΙΟΙ ΓΡΑΦΟΙ
- Algorithms
- AVERAGE CASE ANALYSIS
- Computer network reliability
- Data structures
- DYNAMIC ALGORITHMS
- GRAPH CONNECTIVITY
- Graph theory
- Random graphs
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/8638