Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Σταθόπουλος Γεώργιος. Variants of stable marriage, algorithms, complexity and structural properties. 2011. https://pergamos.lib.uoa.gr/uoa/dl/object/1321458