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

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.

Grantor dc:publisher

Πανεπιστήμιο Πατρών

Year dc:date

1991

Author dc:creator

• Πάντζιου, Γραμματή

• ADAPTIVE PROBABILISTIC TECHNIQUES
• APPROXIMATION SOLUTION
• AVERAGE CASE BEHAVIOR OF ALGORITHMS
• COLORING OF RANDOM GRAPHS
• DISTANCES IN PLANAR GRAPHS
• HAMMOCKS
• MAX CUT PROBLEM
• PRAM ALGORITHM
• PRAM ΑΛΓΟΡΙΘΜΟΣ
• SHORTEST PATHS
• ΑΠΟΣΤΑΣΕΙΣ ΣΕ ΕΠΙΠΕΔΟΥΣ ΓΡΑΦΟΥΣ
• ΕΙΔΙΚΟΙ ΕΞΩΕΠΙΠΕΔΟΙ ΥΠΟΓΡΑΦΟΙ
• ΚΑΤΑ ΜΕΣΗ ΤΙΜΗ ΣΥΜΠΕΡΙΦΟΡΑ ΑΛΓΟΡΙΘΜΩΝ
• ΠΡΟΒΛΗΜΑ ΜΕΓΙΣΤΗΣ ΤΟΜΗΣ
• ΠΡΟΣΑΡΜΟΖΟΜΕΝΕΣ ΠΙΘΑΝΟΤΙΚΕΣ ΤΕΧΝΙΚΕΣ
• ΠΡΟΣΕΓΓΙΣΤΙΚΗ ΛΥΣΗ
• ΣΥΝΤΟΜΟΤΕΡΑ ΜΟΝΟΠΑΤΙΑ
• ΤΕΧΝΙΚΕΣ ΣΧΕΔΙΑΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ
• ΧΡΩΜΑΤΙΣΜΟΣ ΤΥΧΑΙΟΥ ΓΡΑΦΟΥ
• Natural Sciences
• Computer and Information Sciences
• Engineering and Technology
• Electrical Engineering, Electronic Engineering, Information Engineering
• Φυσικές Επιστήμες
• Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
• Επιστήμες Μηχανικού και Τεχνολογία
• Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ

Language dc:language

gre

Identifier

10.12681/eadd/1667

OAI identifier oai:identifier

oai:10442/1667