National and Kapodistrian University of Athens
Variants of stable marriage, algorithms, complexity and structural properties
Abstract
dc:descriptionΤο πρόβλημα του Σταθερού Γάμου, προτάθηκε το 1962 από τους David Gale και Lloyd Sharpley. Από τότε, έχουν υπάρξει πολλά θεωρητικά αποτελέσματα αλλά και πολλές εφαρμογές. Επίσης, έχουν προταθεί αρκετές παραλλαγές του προβλήματος, δημιουργώντας μία πολύ ενδιαφέρουσα κλάση προβλημάτων. Η διπλωματική αυτή είναι μία επισκόπηση της βιβλιογραφίας, σχετικά με το πρόβλημα του Σταθερού Γάμου και των παραλλαγών του και, επικεντρώνεται στα αλγοριθμικά αποτελέσματα αλλά και στα αποτελέσματα πολυπλοκότητας και δομής που έχουν δημοσιευτεί ως τώρα. Επιπλέον, ένα καινούριο αποτέλεσμα παρουσιάζεται. Συγκεκριμένα, υπολογίζεται ένα άνω φράγμα για το μέγιστο πλήθος σταθερών ταιριασμάτων για το πρόβλημα του Σταθερού Γάμου και, μέσω αναγωγών αυτό το φράγμα επεκτείνεται στα προβλήματα Hospital-Residents και Stable Roommates.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Σταθόπουλος Γεώργιος
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1321458