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

Abstract

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).

ΣΤΗΝ ΕΡΓΑΣΙΑ ΑΥΤΗ ΔΙΑΤΥΠΩΝΟΝΤΑΙ ΚΑΙ ΑΝΑΛΥΟΝΤΑΙ ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΘΕΩΡΙΑΣ ΓΡΑΦΗΜΑΤΩΝ ΚΑΙ ΣΥΓΚΕΚΡΙΜΕΝΑ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΤΗΣ ΚΑΤΗΓΟΡΙΑΣ ΤΩΝ ΤΕΛΕΙΩΝ ΓΡΑΦΗΜΑΤΩΝ. ΟΛΟΙ ΟΙ ΑΛΓΟΡΙΘΜΟΙ ΣΤΗΡΙΖΟΝΤΑΙ ΣΕ ΕΝΑ ΝΕΟ ΤΡΟΠΟ ΠΑΡΑΣΤΑΣΗΣ ΤΩΝ ΓΡΑΦΗΜΑΤΩΝ Ο ΟΠΟΙΟΣ ΠΡΟΚΥΠΤΕΙ ΑΠΟ ΤΗΝ ΔΙΑΜΕΡΙΣΗ ΤΟΥ ΣΥΝΟΛΟΥ ΚΟΜΒΩΝ V ΤΟΥ ΓΡΑΦΗΜΑΤΟΣ G=(V,E), ΣΕ ΥΠΟΣΥΝΟΛΑ ΚΟΜΒΩΝ AL(V,L), VEV, 0<L< V , ΜΕ ΧΑΡΑΚΤΗΡΙΣΤΙΚΕΣ ΙΔΙΟΤΗΤΕΣ. ΤΑ ΥΠΟΣΥΝΟΛΑ ΑΥΤΑ ΟΝΟΜΑΣΤΗΚΑΝ "ΣΥΝΟΛΑ ΣΤΑΘΜΩΝ ΓΕΙΤΝΙΑΣΗΣ", ΚΑΙ ΟΙ ΙΔΙΟΤΗΤΕΣ ΤΟΥΣ ΕΠΙΤΡΕΠΟΥΝ ΤΗΝ ΕΚΤΕΛΕΣΗ ΠΡΑΞΕΩΝ ΣΕ ΚΑΘΕ ΤΕΤΟΙΟ ΣΥΝΟΛΟ ΑΝΕΞΑΡΤΗΤΑ ΤΩΝ ΑΛΛΩΝ ΣΥΝΟΛΩΝ. Η ΔΙΑΜΕΡΙΣΗ ΕΝΟΣ ΓΡΑΦΗΜΑΤΟΣ G=(V,E), ΔΗΛΑΔΗ Η ΔΙΑΜΕΡΙΣΗ ΤΟΥ ΣΥΝΟΛΟΥ V, ΕΙΣΑΓΕΙ ΝΕΑ ΧΑΡΑΚΤΗΡΙΣΤΙΚΑ ΜΕΓΕΘΗ ΣΤΟ ΓΡΑΦΗΜΑ. ΤΑ ΜΕΓΕΘΗ ΑΥΤΑ ΕΙΝΑΙ ΤΟ ΜΗΚΟΣ L ΚΑΙ ΤΟ ΥΨΟΣ H ΤΟΥ ΓΡΑΦΗΜΑΤΟΣ. ΟΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΧΡΟΝΟΥ Τ(4) ΚΑΙ ΕΠΕΞΕΡΓΑΣΤΩΝ Ρ(4) ΤΩΝ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΔΙΔΕΤΕ ΣΑΝ ΣΥΝΑΡΤΗΣΗ ΤΩΝ ΜΕΓΕΘΩΝ L, H ΚΑΙ N,ΟΠΟΥ L<N, H<N ΚΑΙ N= V. ΤΟ ΥΠΟΛΟΓΙΣΤΙΚΟ ΠΡΟΤΥΠΟ ΤΗΣ ΜΕΛΕΤΗΣ ΕΙΝΑΙ ΕΝΑ PARALLELRANDOM ACCESS MACHINE ΤΥΠΟΥ CRCW-PRAM.