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

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.

Grantor dc:publisher

University of Patras

Year dc:date

1991

Author dc:creator

• Ζαρολιάγκης, Χρήστος

• ΑΝΑΛΥΣΗ ΜΕΣΗΣ ΣΥΜΠΕΡΙΦΟΡΑΣ ΑΛΓΟΡΙΘΜΟΥ
• ΑΝΑΛΥΣΗ ΧΕΙΡΟΤΕΡΗΣ ΣΥΜΠΕΡΙΦΟΡΑΣ ΑΛΓΟΡΙΘΜΟΥ
• ΕΠΙΠΕΔΟΙ ΓΡΑΦΟΙ
• ΜΟΝΤΕΛΟ PRAM
• Παράλληλοι αλγόριθμοι
• ΣΥΝΤΟΜΟΤΕΡΟ ΜΟΝΟΠΑΤΙ
• ΤΥΧΑΙΟΙ ΓΡΑΦΟΙ
• AVERAGE CASE ANALYSIS
• Parallel algorithms
• PLANAR GRAPHS
• PRAM MODEL
• Random graphs
• SHORTEST PATH
• WORST CASE ANALYSIS
• Φυσικές Επιστήμες
• Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
• Επιστήμες Μηχανικού και Τεχνολογία
• Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
• Natural Sciences
• Computer and Information Sciences
• Engineering and Technology
• Electrical Engineering, Electronic Engineering, Information Engineering

Language dc:language

gre

Identifier

10.12681/eadd/1668

OAI identifier oai:identifier

oai:10442/1668