{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2958609"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2958609","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Extendability of Graphs with Perfect Matchings","abstract":"Ταίριασμα ενός γραφήματος είναι ένα σύνολο ακμών οι οποίες δεν έχουν κανένα κοινό άκρο και λέγεται τέλειο εάν κάθε κορυφή του γραφήματος προσπίτει σε κάποια ακμή του ταιριάσματος. Σκοπός της διπλωματικής είναι η μελέτη αλγοριθμικών και δομικών ιδιοτήτων γραφημάτων με τέλεια ταιριάσματα. Συγκεκριμένα, εστιάζουμε στην ακόλουθη ερώτηση: Υποθέτοντας ότι το k είναι ένας θετικός ακέραιος και G είναι ένα γράφημα, είναι το G k-επεκτάσιμο; Δηλαδή, είναι αλήθες ότι για κάθε ταίριασμα M στο G πληθυκότητας k υπάρχει κάποιο τέλειο ταίριασμα που περιέχει όλες τις ακμές του M; Υπάρχει άμεση συσχέτιση στον δομικό χαρακτηρισμό των k-επεκτάσιμων διμερών γραφημάτων G με τέλεια ταιριάσματα και στην ύπαρξη k ξένων μονοπατιών, που είναι ανάλογο του θεωρήματος του Menger. Από υπολογιστικής απόψεως, το Extendability πρόβλημα εστιάζει στο εάν ένα γράφημα G είναι k-επεκτάσιμο. Στην γενική περίπτωση, αυτό το πρόβλημα είναι coNP-πλήρες. Στην περίπτωση όπου το G είναι διμερές, υπάρχει πολυωνυμικός αλγόριθμος που το αποφασίζει.","abstract_html":"Ταίριασμα ενός γραφήματος είναι ένα σύνολο ακμών οι οποίες δεν έχουν κανένα κοινό άκρο και λέγεται τέλειο εάν κάθε κορυφή του γραφήματος προσπίτει σε κάποια ακμή του ταιριάσματος. Σκοπός της διπλωματικής είναι η μελέτη αλγοριθμικών και δομικών ιδιοτήτων γραφημάτων με τέλεια ταιριάσματα. Συγκεκριμένα, εστιάζουμε στην ακόλουθη ερώτηση: Υποθέτοντας ότι το k είναι ένας θετικός ακέραιος και G είναι ένα γράφημα, είναι το G k-επεκτάσιμο; Δηλαδή, είναι αλήθες ότι για κάθε ταίριασμα M στο G πληθυκότητας k υπάρχει κάποιο τέλειο ταίριασμα που περιέχει όλες τις ακμές του M; Υπάρχει άμεση συσχέτιση στον δομικό χαρακτηρισμό των k-επεκτάσιμων διμερών γραφημάτων G με τέλεια ταιριάσματα και στην ύπαρξη k ξένων μονοπατιών, που είναι ανάλογο του θεωρήματος του Menger. Από υπολογιστικής απόψεως, το Extendability πρόβλημα εστιάζει στο εάν ένα γράφημα G είναι k-επεκτάσιμο. Στην γενική περίπτωση, αυτό το πρόβλημα είναι coNP-πλήρες. Στην περίπτωση όπου το G είναι διμερές, υπάρχει πολυωνυμικός αλγόριθμος που το αποφασίζει.","abstract_has_math":false,"creators":["Σεμερτζάκης Γεώργιος","Semertzakis Georgios"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021","date_published":"2021","updated_at":"2026-11-19T05:43:34Z","subjects":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"languages":["Ελληνικά","English","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2958609"],"render_values":[{"text":"uoadl:2958609","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2958609","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2958609","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A2958609","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Σεμερτζάκης Γεώργιος","Semertzakis Georgios"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Τεχνολογία – Πληροφορική","Technology - Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","English","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2958609","https://pergamos.lib.uoa.gr/uoa/dl/object/2958609"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ταίριασμα ενός γραφήματος είναι ένα σύνολο ακμών οι οποίες δεν έχουν κανένα κοινό άκρο και λέγεται τέλειο εάν κάθε κορυφή του γραφήματος προσπίτει σε κάποια ακμή του ταιριάσματος. Σκοπός της διπλωματικής είναι η μελέτη αλγοριθμικών και δομικών ιδιοτήτων γραφημάτων με τέλεια ταιριάσματα. Συγκεκριμένα, εστιάζουμε στην ακόλουθη ερώτηση: Υποθέτοντας ότι το k είναι ένας θετικός ακέραιος και G είναι ένα γράφημα, είναι το G k-επεκτάσιμο; Δηλαδή, είναι αλήθες ότι για κάθε ταίριασμα M στο G πληθυκότητας k υπάρχει κάποιο τέλειο ταίριασμα που περιέχει όλες τις ακμές του M; Υπάρχει άμεση συσχέτιση στον δομικό χαρακτηρισμό των k-επεκτάσιμων διμερών γραφημάτων G με τέλεια ταιριάσματα και στην ύπαρξη k ξένων μονοπατιών, που είναι ανάλογο του θεωρήματος του Menger. Από υπολογιστικής απόψεως, το Extendability πρόβλημα εστιάζει στο εάν ένα γράφημα G είναι k-επεκτάσιμο. Στην γενική περίπτωση, αυτό το πρόβλημα είναι coNP-πλήρες. Στην περίπτωση όπου το G είναι διμερές, υπάρχει πολυωνυμικός αλγόριθμος που το αποφασίζει.","A matching of a graph is a set of pairwise disjoint edges and it is called perfect if every vertex of the graph is incident to some edge of the matching. The purpose of this thesis is the study of structural and algorithmic properties of graphs with perfect matchings. In particular, we focus on the following question: Assuming that k is a positive integer and G is a graph with perfect matching, is G k-extendable? That is, is it true that for every matching M of cardinality k in G there exists a perfect matching that entirely contains M? There is a detailed structural characterization of bipartite graphs G with perfect matchings in terms of the existence of disjoint paths with certain properties which is a direct analogue of Menger's theorem. From a computational perspective, the Extendability problem focuses on the question whether a graph G is k-extendable or not. In the general case, this problem is coNP-complete. In the case where graph G is bipartite, there is a polynomial algorithm that decides it."]},{"key":"dc:title","label":"Title","values":["Extendability of Graphs with Perfect Matchings"]}]}],"canonical_facts":{"dc:creator":["Σεμερτζάκης Γεώργιος","Semertzakis Georgios"],"dc:date":["2021"],"dc:description":["Ταίριασμα ενός γραφήματος είναι ένα σύνολο ακμών οι οποίες δεν έχουν κανένα κοινό άκρο και λέγεται τέλειο εάν κάθε κορυφή του γραφήματος προσπίτει σε κάποια ακμή του ταιριάσματος. Σκοπός της διπλωματικής είναι η μελέτη αλγοριθμικών και δομικών ιδιοτήτων γραφημάτων με τέλεια ταιριάσματα. Συγκεκριμένα, εστιάζουμε στην ακόλουθη ερώτηση: Υποθέτοντας ότι το k είναι ένας θετικός ακέραιος και G είναι ένα γράφημα, είναι το G k-επεκτάσιμο; Δηλαδή, είναι αλήθες ότι για κάθε ταίριασμα M στο G πληθυκότητας k υπάρχει κάποιο τέλειο ταίριασμα που περιέχει όλες τις ακμές του M; Υπάρχει άμεση συσχέτιση στον δομικό χαρακτηρισμό των k-επεκτάσιμων διμερών γραφημάτων G με τέλεια ταιριάσματα και στην ύπαρξη k ξένων μονοπατιών, που είναι ανάλογο του θεωρήματος του Menger. Από υπολογιστικής απόψεως, το Extendability πρόβλημα εστιάζει στο εάν ένα γράφημα G είναι k-επεκτάσιμο. Στην γενική περίπτωση, αυτό το πρόβλημα είναι coNP-πλήρες. Στην περίπτωση όπου το G είναι διμερές, υπάρχει πολυωνυμικός αλγόριθμος που το αποφασίζει.","A matching of a graph is a set of pairwise disjoint edges and it is called perfect if every vertex of the graph is incident to some edge of the matching. The purpose of this thesis is the study of structural and algorithmic properties of graphs with perfect matchings. In particular, we focus on the following question: Assuming that k is a positive integer and G is a graph with perfect matching, is G k-extendable? That is, is it true that for every matching M of cardinality k in G there exists a perfect matching that entirely contains M? There is a detailed structural characterization of bipartite graphs G with perfect matchings in terms of the existence of disjoint paths with certain properties which is a direct analogue of Menger's theorem. From a computational perspective, the Extendability problem focuses on the question whether a graph G is k-extendable or not. In the general case, this problem is coNP-complete. In the case where graph G is bipartite, there is a polynomial algorithm that decides it."],"dc:identifier":["uoadl:2958609","https://pergamos.lib.uoa.gr/uoa/dl/object/2958609"],"dc:language":["Ελληνικά","English","Greek"],"dc:subject":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"dc:title":["Extendability of Graphs with Perfect Matchings"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:43:34Z"}