Μονάδα:
Τμήμα Πληροφορικής & ΤηλεπικοινωνιώνΠληροφορική
Ημερομηνία κατάθεσης:
2022-07-04
Συγγραφέας:
ΠΑΡΩΝΗΣ ΑΝΤΩΝΙΟΣ
Στοιχεία επιβλεπόντων καθηγητών:
Σταύρος Κολλιόπουλος, Καθηγητής, Πληροφορικής & Τηλεπικοινωνιών, Εθνικό & Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
Μελέτη Αλγορίθμων Κατασκευής Δέντρων Gomory-Hu
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
Μελέτη Αλγορίθμων Κατασκευής Δέντρων Gomory-Hu
Περίληψη:
Το παρόν έργο αποτελεί μια μελέτη πάνω στην έρευνα των Α. Bhalgat, R. Hariharan, T. Kavitha και D. Panigrahi "An Õ(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs".
Παρουσιάζουμε τις έννοιες της ροής σε γραφήματα, το πρόβλημα της μέγιστης ροής σε γραφήματα με πολλαπλά τερματικά, καθώς και την έννοια του δέντρου Gomory-Hu, με μια συνοπτική απόδειξη για την ορθότητα του.
Αφού εισάγουμε τις αναγκαίες έννοιες, παρουσιάζουμε δύο αποδοτικούς αλγόριθμους ακμοσυνεκτικότητας και Steiner ακμοσυνεκτικότητας , και πώς μπορεί ο τελευταίος να χρησιμοποιηθεί για την κατασκευή δέντρων Gomory-Hu για μη κατευθυνόμενα και μη έμβαρα γραφήματα σε σχεδόν γραμμικό χρόνο Õ(mn).
Τέλος, παρουσιάζουμε αποτελέσματα που έχουν προκύψει από μεταγενέστερες έρευνες που έχουν γίνει πάνω στα Gomory-Hu δέντρα, μερικές πρακτικές τους εφαρμογές καθώς και τα ανοιχτά προβλήματα πάνω σε αυτή τη θεματική περιοχή.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
Δέντρα Gomory-Hu, Μέγιστη Ροή - Ελάχιστη Τομή, Ακμοσυνεκτικότητα, Ακμοσυνεκτικότητα Steiner, Μέγιστη Ροή Πολλαπλών Τερματικών
Αρ. σελίδων ευρετηρίου:
2
Αρ. βιβλιογραφικών αναφορών:
24
