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

Περίληψη

ΣΤΗΝ ΕΡΓΑΣΙΑ ΑΥΤΗ ΔΙΑΤΥΠΩΝΟΝΤΑΙ ΚΑΙ ΑΝΑΛΥΟΝΤΑΙ ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΘΕΩΡΙΑΣ ΓΡΑΦΗΜΑΤΩΝ ΚΑΙ ΣΥΓΚΕΚΡΙΜΕΝΑ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΤΗΣ ΚΑΤΗΓΟΡΙΑΣ ΤΩΝ ΤΕΛΕΙΩΝ ΓΡΑΦΗΜΑΤΩΝ. ΟΛΟΙ ΟΙ ΑΛΓΟΡΙΘΜΟΙ ΣΤΗΡΙΖΟΝΤΑΙ ΣΕ ΕΝΑ ΝΕΟ ΤΡΟΠΟ ΠΑΡΑΣΤΑΣΗΣ ΤΩΝ ΓΡΑΦΗΜΑΤΩΝ Ο ΟΠΟΙΟΣ ΠΡΟΚΥΠΤΕΙ ΑΠΟ ΤΗΝ ΔΙΑΜΕΡΙΣΗ ΤΟΥ ΣΥΝΟΛΟΥ ΚΟΜΒΩΝ 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.

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

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).
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

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

DOI
10.12681/eadd/2102
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/2102
ND
2102
Εναλλακτικός τίτλος
PARALLEL ALGORITMHS FOR PROBLEMS ON PERFECT GRAPHS
Συγγραφέας
ΝΙΚΟΛΟΠΟΥΛΟΣ, ΣΤΑΥΡΟΣ
Ημερομηνία
1991
Ίδρυμα
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Εξεταστική επιτροπή
ΔΑΝΙΗΛΟΠΟΥΛΟΣ ΣΤΥΛΙΑΝΟΣ
ΝΟΥΤΣΟΣ ΔΗΜΗΤΡΙΟΣ
ΛΕΟΝΤΙΤΣΗΣ ΑΝΔΡΕΑΣ
ΓΙΑΝΝΑΚΟΥΔΑΚΗΣ ΕΜΜΑΝΟΥΗΛ
ΤΣΟΥΡΟΣ ΚΩΝΣΤΑΝΤΙΝΟΣ
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Μαθηματικά
Λέξεις-κλειδιά
ΔΙΑΜΕΡΙΣΗ ΓΡΑΦΗΜΑΤΟΣ; ΔΙΑΣΠΑΣΗΜΑ ΓΡΑΦΗΜΑΤΑ; Παράλληλοι αλγόριθμοι; ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΧΡΟΝΟΥ ΚΑΙ ΕΠΕΞΕΡΓΑΣΤΩΝ; ΤΡΙΓΩΝΙΚΑ ΓΡΑΦΗΜΑΤΑ
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά