Back to search

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 × 2

Rights

Language dc:language
Ελληνικά, English, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:2958609

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
citation

Σεμερτζάκης Γεώργιος; Semertzakis Georgios. Extendability of Graphs with Perfect Matchings. 2021. https://pergamos.lib.uoa.gr/uoa/dl/object/2958609