Small Vertex Cut on the PRAM model

Abstract

Το πρόβλημα Vertex Cut αφορά την εύρεση του ελάχιστου συνόλου κορυφών, η αφαίρεση των οποίων αποσυνδέει ένα γράφημα σε πολλαπλές συνεκτικές συνιστώσες. Είναι ένα θεμελιώδες πρόβλημα στην επιστήμη υπολογιστών καθώς έχει πολυάριθμες εφαρμογές, όπως ο σχεδιασμός ανθεκτικών σε σφάλματα δικτύων, οι παράλληλοι υπολογισμοί και τα κατανεμημένα συστήματα. Καθώς το μέγεθος και η πολυπλοκότητα των δεδομένων αυξάνονται εκθετικά, η αντιμετώπιση του προβλήματος κοπής κορυφών σε ένα παράλληλο υπολογιστικό περιβάλλον καθίσταται απαραίτητη για την επίτευξη κλιμακούμενων και αποδοτικών λύσεων. Σε αυτή τη διπλωματική εργασία εξετάζουμε το πρόβλημα Vertex Cut στο πλαίσιο των παράλληλων υπολογισμών, και συγκεκριμένα στο μοντέλο PRAM. Ξεκινάμε παρουσιά- ζοντας διάφορες προαπαιτούμενες έννοιες, όπως το μοντέλο PRAM, την ανάλυση πολυ- πλοκότητας παράλληλων αλγορίθμων στο μοντέλο work/depth και θεμελιώδη αποτελέ- σματα στο μοντέλο PRAM και το πρόβλημα vertex connectivity. Στη συνέχεια, παρου- σιάζουμε τους κλασικούς αλγόριθμους για την επίλυση του προβλήματος στο σειριακό μοντέλο RAM, και ακολουθούμε την πορεία εργασιών των Nanongkai, Thatchaphol και Yingchareonthawornchai, οι οποίοι ήταν οι πρώτοι που έσπασαν το τετραγωνικό φράγμα για την πολυπλοκότητα του πρόβληματος. Για να μεταφέρουμε αυτές τις ιδέες στο παράλληλο μοντέλο, αντιμετωπίζουμε το εμπό- διο της παράλληλης προσπελασιμότητας, το οποίο επιλύουμε χρησιμοποιώντας τεχνικές από την εργασία των Sidford, Jambulapati και Liu. Συγκεκριμένα, κατασκευάζουμε hopsets για να μειώσουμε τη διάμετρο του γραφήματος, καθιστώντας το προσπελάσιμο με μικρό depth. Τέλος, συνδυάζουμε αυτές τις ιδέες και παρουσιάζουμε δύο αλγορίθμους με work/depth tradeoff για αυτό το πρόβλημα και εξετάζουμε πιθανές κατευθύνσεις για μελλοντική έρευνα.