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

Abstract

IN THIS THESIS, WE PROVIDE NEW TECHNIQUES FOR THE DESIGN AND ANALYSIS OF PARALLEL ALGORITHMS AND THEIR APPLICATION TO GRAPH PROBLEMS. MORE PRECISELY: 1. WE PRESENT A DETERMINISTIC TECHNIQUE BASED ON THE DECOMPOSITION OF A PLANAR DIGRAPH INTO SPECIAL OUTERPLANAR SUBGRAPHS CALLED HAMMOCKS. 2. WE PRESENT A PROBABILISTIC TECHNIQUE FOR FINDING PARALLEL APPROXIMATION SOLUTIONS FOR NP-HARD PROBLEMS.3. NEW "ADAPTIVE" PROBABILISTIC TECHNIQUES ARE PRESENTED FOR THE AVERAGE-CASE ANALYSIS OF PARALLEL ALGORITHMS. WE USE THE ABOVE TECHNIQUES FOR THE DESIGN ANDANALYSIS OF EFFICIENT PARALLEL ALGORITHMS FOR THE FOLLOWING PROBLEMS: 1. FINDING SHORTEST PATHS AND DISTANCES IN PLANAR DIGRAPH. 2. FINDING AN APPROXIMATION SOLUTION FOR THE ENUMERATION VERSION OF THE MAX CUT PROBLEM. 3. COLORING OF RANDOM GRAPHS.

ΣΤΗΝ ΠΑΡΟΥΣΑ ΔΙΑΤΡΙΒΗ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΝΕΕΣ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΟ ΣΧΕΔΙΑΣΜΟ ΚΑΙ ΤΗΝ ΑΝΑΛΥΣΗ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΚΑΙ ΤΗΝ ΕΦΑΡΜΟΓΗ ΤΟΥ ΣΕ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ. ΠΙΟ ΣΥΓΚΕΚΡΙΜΕΝΑ: 1. ΠΑΡΟΥΣΙΑΖΕΤΑΙ ΜΙΑ ΝΤΕΤΕΡΜΙΝΙΣΤΙΚΗ ΤΕΧΝΙΚΗ ΠΟΥ ΒΑΣΙΖΕΤΑΙ ΣΤΗ ΔΙΑΣΠΑΣΗΕΝΟΣ ΕΠΙΠΕΔΟΥ ΚΑΤΕΥΘΥΝΟΜΕΝΟΥ ΓΡΑΦΟΥ ΣΤΟΥΣ ΕΙΔΙΚΟΥΣ ΕΞΩΕΠΙΠΕΔΟΥΣ ΥΠΟΓΡΑΦΟΥΣ ΤΟΥ. 2. ΑΝΑΠΤΥΣΣΕΤΑΙ ΜΙΑ ΠΙΘΑΝΟΤΙΚΗ ΤΕΧΝΙΚΗ ΓΙΑ ΤΗΝ ΕΥΡΕΣΗ ΠΑΡΑΛΛΗΛΩΝ ΠΡΟΣΕΓΓΙΣΤΙΚΩΝ ΛΥΣΕΩΝ ΣΕ ΝΡ-ΔΥΣΚΟΛΑ ΠΡΟΒΛΗΜΑΤΑ. 3. ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΝΕΕΣ "ΠΡΟΣΑΡΜΟΖΟΜΕΝΕΣ" ΠΙΘΑΝΟΤΙΚΕΣ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΗΝ ΑΝΑΛΥΣΗ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΠΡΟΚΕΙΜΕΝΟΥ ΝΑ ΠΡΟΣΔΙΟΡΙΣΘΕΙ Η ΚΑΤΑ ΜΕΣΗ ΤΙΜΗ ΣΥΜΠΕΡΙΦΟΡΑ ΤΟΥΣ. ΧΡΗΣΙΜΟΠΟΙΟΥΜΕ ΤΙΣ ΠΑΡΑΠΑΝΩ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΟ ΣΧΕΔΙΑΣΜΟ ΚΑΙ ΤΗΝ ΑΝΑΛΥΣΗ ΑΠΟΔΟΤΙΚΩΝ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΓΙΑ ΤΑ ΕΞΗΣ ΠΡΟΒΛΗΜΑΤΑ: 1. ΥΠΟΛΟΓΙΣΤΕΣ ΣΥΝΤΟΜΟΤΕΡΩΝ ΜΟΝΟΠΑΤΙΩΝ ΚΑΙ ΑΠΟΣΤΑΣΕΩΝ ΣΕ ΕΠΙΠΕΔΟΥΣ ΚΑΤΕΥΘΥΝΟΜΕΝΟΥΣ ΓΡΑΦΟΥΣ. 2. ΕΥΡΕΣΗ ΠΡΟΣΕΓΓΙΣΤΙΚΗΣ ΛΥΣΗΣ ΓΙΑ ΤΗΝ ΕΚΔΟΣΗ ΑΠΑΡΙΘΜΗΣΗΣ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ ΤΗΣ ΜΕΓΙΣΤΗΣ ΤΟΜΗΣ. 3. ΧΡΩΜΑΤΙΣΜΟΣ ΤΥΧΑΙΩΝ ΓΡΑΦΩΝ.