Back to search

National and Kapodistrian University of Athens

Sphere-cut decompositions and dominating sets in planar graphs

Abstract

dc:description

Ένα σημαντικό αποτέλεσμα στη Θεωρία Γραφημάτων αποτελεί η απόδειξη της εικασίας του Wagner απο τους Neil Robertson και Paul. D. Seymour στη σειρά εργασιών "Ελλάσονα Γραφήματα" απο το 1983 εώς το 2011. Η εικασία αυτή λέει ότι στην κλάση των γραφημάτων δεν υπάρχει άπειρη αντιαλυσίδα ως προς τη σχέση των ελλασόνων γραφημάτων. Η Θεωρία που αναπτύχθηκε για την απόδειξη αυτής της εικασίας είχε και έχει ακόμα σημαντικό αντίκτυπο τόσο στην δομική όσο και στην αλγοριθμική Θεωρία Γραφημάτων, άλλα και σε άλλα πεδία όπως η Παραμετρική Πολυπλοκότητα. Στα πλαίσια της απόδειξης οι συγγραφείς εισήγαγαν και νέες παραμέτρους πλάτους. Σε αυτές ήταν η κλαδοαποσύνθεση και το κλαδοπλάτος ενός γραφήματος. Η παράμετρος αυτή χρησιμοποιήθηκε ιδιαίτερα στο σχεδιασμό αλγορίθμων και στην χρήση της τεχνικής "διαίρει και βασίλευε". Επιπλέον εισήχθησαν νέες παρεμφερείς έννοιες όπως οι αποσυνθέσεις σφαιρικών τομών που είναι κλαδοαποσυνθέσεις στην κλάση των επίπεδων γραφημάτων που έχουν κάποιες επιπλέον ιδιότητες. Στην εξέλιξη της έρευνας υπήρξαν σημαντικά αποτέλεσμα σχετικά με το κλαδοπλάτος στην κλάση των επίπεδων γραφημάτων. Οι Fedor. V. Fomin και Δημήτριος Μ. Θηλυκός απέδειξαν ότι το κλαδοπλάτος ενός επίπεδου γραφήματος με n κορυφές είναι το πολύ \sqrt{4.5\cdot n}. Βασιζόμενος σε αυτό το αποτέλεσμα, ο Δημήτριος Μ. Θηλυκός συσχέτισε το κλαδοπλάτος με μια άλλη παράμετρο σε επίπεδα γραφήματα, το r-ακτινικό σύνολο κυριαρχίας. Απέδειξε ότι αν εμβαπτισμένο επίπεδο γράφημα έχει r- ακτινικό σύνολο κυριαρχίας το πολύ k, τότε το κλαδοπλάτος του γραφήματος θα είναι το πολύ r\cdot\sqrt{4.5\cdot k}. H παρούσα διπλωματική εργασία κάνει μια ποιοτική επέκταση του αυτού του αποτελέσματος. Αποδεικνύουμε ότι το παραπάνω όριο μπορεί να αναζητηθεί σε ένα δάσος που είναι υπογράφημα του δέντρου μιας αποσύνθεσης σφαιρικών τομών του γραφήματος όπου το μέγεθος του είναι γραμμικό ως προς το k.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Σάμαρης Μιχάλης

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1321387

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

Σάμαρης Μιχάλης. Sphere-cut decompositions and dominating sets in planar graphs. 2016. https://pergamos.lib.uoa.gr/uoa/dl/object/1321387