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

Περίληψη

ΣΤΗΝ ΠΑΡΟΥΣΑ ΔΙΑΤΡΙΒΗ ΑΝΑΠΤΥΣΣΟΝΤΑΙ ΓΡΗΓΟΡΟΙ, ΒΕΛΤΙΣΤΟΙ 'Η/ΚΑΙ ΑΠΟΔΟΤΙΚΟΙ ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ ΟΙ ΟΠΟΙΟΙ ΒΕΛΤΙΩΝΟΥΝ ΣΗΜΑΝΤΙΚΑ ΤΙΣ ΠΟΛΥΠΛΟΚΟΤΗΤΕΣ ΤΩΝ ΠΡΟΗΓΟΥΜΕΝΩΝ ΚΑΛΥΤΕΡΩΝ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΓΙΑ ΤΑ ΙΔΙΑ ΠΡΟΒΛΗΜΑΤΑ. ΠΙΟ ΣΥΓΚΕΚΡΙΜΕΝΑ ΕΞΕΤΑΖΟΥΜΕ, (Α) ΤΗΝ ΧΕΙΡΟΤΕΡΗ ΠΑΡΑΛΛΗΛΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΚΥΡΙΩΣ ΠΡΟΒΛΗΜΑΤΩΝ ΧΡΩΜΑΤΙΣΜΟΥ ΚΑΙ ΕΥΡΕΣΗΣ ΣΥΝΤΟΜΟΤΕΡΩΝ ΜΟΝΟΠΑΤΙΩΝ ΣΕ ΑΡΑΙΟΥΣ (Π.Χ.ΕΠΙΠΕΔΟΥΣ) ΓΡΑΦΟΥΣ, ΚΑΙ (Β) ΤΗΝ ΜΕΣΗ ΠΑΡΑΛΛΗΛΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΕΝΟΣ ΠΡΟΒΛΗΜΑΤΟΣ ΧΡΩΜΑΤΙΣΜΟΥ ΓΡΑΦΩΝ ΤΟ ΟΠΟΙΟ ΕΙΝΑΙ ΝΡ-ΠΛΗΡΕΣ ΩΣ ΠΡΟΣ ΤΗΝ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΧΕΙΡΟΤΕΡΗΣ ΠΕΡΙΠΤΩΣΗΣ. ΟΙ ΑΛΓΟΡΙΘΜΟΙ ΧΑΡΑΚΤΗΡΙΖΟΝΤΑΙ ΑΠΟ ΜΙΑ ΔΟΜΙΚΗ ΕΞΑΡΤΗΣΗ, ΜΕ ΤΗΝ ΕΝΝΟΙΑ ΟΤΙ ΓΙΑ ΝΑ ΛΥΣΟΥΜΕ ΤΑ ΠΙΟ ΣΥΝΘΕΤΑ ΠΡΟΒΛΗΜΑΤΑ ΔΙΝΟΥΜΕ ΠΡΩΤΑ ΛΥΣΕΙΣ ΣΕ ΒΑΣΙΚΑΚΑΙ ΠΙΟ ΑΠΛΑ ΠΡΟΒΛΗΜΑΤΑ . ΑΥΤΗ Η ΔΟΜΗ ΕΙΝΑΙ ΑΡΚΕΤΑ ΣΗΜΑΝΤΙΚΗ ΣΤΟ ΣΧΕΔΙΑΣΜΟ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ.

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

IN THIS THESIS FAST, OPTIMAL AND/OR EFFICIENT PARALLEL ALGORITHMS ARE DEVELOPEDFOR MANY IMPORTANT GRAPH PROBLEMS WHICH IMPROVE SIGNIFICANTLY THE COMPLEXITIESOF THE BEST PREVIOUS KNOWN PARALLEL ALGORITHMS ON THE SAME PROBLEMS. MORE PRECISELY WE INVESTIGATE, (I) THE WORST-CASE PARALLEL COMPLEXITY MOSTLY OF COLORINGAND SHORTEST PATH PROBLEMS IN SPARSE (E.G. PLANAR) GRAPHS, AND (II) THE AVERAGE-CASE PARALLEL COMPLEXITY OF A GRAPH COLORING PROBLEM WHICH IS KNOWN TO BE NP-COMPLETE IN THE WORST CASE. THE ALGORITHMS CAN BE CHARACTERIZED IN A STRUCTURALWAY, IN THE SENSE THAT IN ORDER TO SOLVE THE MORE INVOLVED PROBLEMS, WE FIRST GIVE SOLUTIONS TO SOME BASIC UNDERLYING ONES. THIS STRUCTURE SEEMS TO BE IMPORTANT IN THE DESIGN OF PARALLEL ALGORITHMS.
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

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

DOI
10.12681/eadd/1668
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/1668
Εναλλακτικός τίτλος
WORST AND AVERAGE CASE BEHAVIOUR OF PARALLEL ALGORITHMS FOR GRAPH PROBLEMS
Συγγραφέας
ΖΑΡΟΛΙΑΓΚΗΣ, ΧΡΗΣΤΟΣ
Ημερομηνία
1991
Ίδρυμα
Πανεπιστήμιο Πατρών. Σχολή Πολυτεχνική. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Εξεταστική επιτροπή
ΣΠΥΡΑΚΗΣ ΠΑΥΛΟΣ
ΠΑΠΑΘΕΟΔΩΡΟΥ ΘΕΟΔΩΡΟΣ
ΚΥΡΟΥΣΗΣ ΕΛΕΥΘΕΡΙΟΣ
ΤΣΑΚΑΛΙΔΗΣ ΑΘΑΝΑΣΙΟΣ
ΖΑΧΟΣ ΕΥΣΤΑΘΙΟΣ
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμες Ηλεκτρονικών Υπολογιστών & Πληροφορικής
Μηχανική & Τεχνολογία
Επιστήμες Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού & Μηχανικού Η/Υ
Λέξεις-κλειδιά
ΑΝΑΛΥΣΗ ΜΕΣΗΣ ΣΥΜΠΕΡΙΦΟΡΑΣ ΑΛΓΟΡΙΘΜΟΥ; ΑΝΑΛΥΣΗ ΧΕΙΡΟΤΕΡΗΣ ΣΥΜΠΕΡΙΦΟΡΑΣ ΑΛΓΟΡΙΘΜΟΥ; ΕΠΙΠΕΔΟΙ ΓΡΑΦΟΙ; ΜΟΝΤΕΛΟ PRAM; Παράλληλοι αλγόριθμοι; ΣΥΝΤΟΜΟΤΕΡΟ ΜΟΝΟΠΑΤΙ; ΤΥΧΑΙΟΙ ΓΡΑΦΟΙ
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά