National and Kapodistrian University of Athens
Extendability of Graphs with Perfect Matchings
Abstract
dc:descriptionΤαίριασμα ενός γραφήματος είναι ένα σύνολο ακμών οι οποίες δεν έχουν κανένα κοινό άκρο και λέγεται τέλειο εάν κάθε κορυφή του γραφήματος προσπίτει σε κάποια ακμή του ταιριάσματος. Σκοπός της διπλωματικής είναι η μελέτη αλγοριθμικών και δομικών ιδιοτήτων γραφημάτων με τέλεια ταιριάσματα. Συγκεκριμένα, εστιάζουμε στην ακόλουθη ερώτηση: Υποθέτοντας ότι το k είναι ένας θετικός ακέραιος και G είναι ένα γράφημα, είναι το G k-επεκτάσιμο; Δηλαδή, είναι αλήθες ότι για κάθε ταίριασμα M στο G πληθυκότητας k υπάρχει κάποιο τέλειο ταίριασμα που περιέχει όλες τις ακμές του M; Υπάρχει άμεση συσχέτιση στον δομικό χαρακτηρισμό των k-επεκτάσιμων διμερών γραφημάτων G με τέλεια ταιριάσματα και στην ύπαρξη k ξένων μονοπατιών, που είναι ανάλογο του θεωρήματος του Menger. Από υπολογιστικής απόψεως, το Extendability πρόβλημα εστιάζει στο εάν ένα γράφημα G είναι k-επεκτάσιμο. Στην γενική περίπτωση, αυτό το πρόβλημα είναι coNP-πλήρες. Στην περίπτωση όπου το G είναι διμερές, υπάρχει πολυωνυμικός αλγόριθμος που το αποφασίζει.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Σεμερτζάκης Γεώργιος
- Semertzakis Georgios
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, English, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:2958609