Back to search

University of Patras

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

Abstract

dc:description

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.

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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/8638

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

Νικολετσέας, Σωτήρης. ΖΗΤΗΜΑΤΑ ΣΥΝΕΚΤΙΚΟΤΗΤΑΣ ΣΕ ΤΥΧΑΙΟΥΣ ΓΡΑΦΟΥΣ. University of Patras, 1997. http://hdl.handle.net/10442/hedi/8638