Back to search

University of Ioannina

ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΤΕΛΕΙΩΝ ΓΡΑΦΗΜΑΤΩΝ

Abstract

dc:description

IN THIS RESEARCH WORK, PARALLEL ALGORITHMS ARE DESIGNED AND ANALYSED FOR GRAPH THEORETIC PROBLEMS, PARTICULARLY FOR PROBLEMS ON PERFECT GRAPHS. ALL ALGORITHMSARE BASED ON A NEW PRESENTATION OF THE UNDIRECTED GRAPHS. THE VERTEX SET V OF A GRAPH G=(V,E) IS PARTITIONED INTO SUBSETS, IN A SPECIFIC FASHION. WE CALL THESE SUBSETS "ADJACENCY LEVEL SETS" AND DENOTE AL(V,L), VEV, 0<L< V . THEIR PROPERTIES ALLOW SOME SET OPERATIONS TO BE EXECUTED INDEPENDENTLY IN EACH ONE OF THESE SUBSETS, AND THEREFORE PARALLEL. THE PARTITION OF A GRAPH G=(V,E), I.E. THE PARTITION OF THE VERTEX SET V, INTRODUCES NEW CHARACTERISTIC MEASURES. THESE MEASURES ARE THE LENGTH AND THE HEIGHT H OF THE GRAPH. THE ASYMPTOTIC TIME COMPLEXITY T(N) OF ALL PARALLEL ALGORITHMS IS GIVEN AS A FUNCTION OF THE MEASURES L AND H, WHILE THE PROCESSOR COMPLEXITY P(N) ON A FUNCTION OF THE MEASURES L AND N, WHERE L<N, H<N AND N= V . THE COMPUTATIONAL MODEL USED IN THIS WORK IS A CRCWPARALLEL RANDOM ACCESS MACHINE (CRCW-PRAM).

Degree

thesis:*
Grantor dc:publisher
University of Ioannina
Year dc:date
1991

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Νικολόπουλος, Σταύρος

Subjects

dc:subject × 15

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/2102

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 Ioannina, 1991. http://hdl.handle.net/10442/hedi/2102