Back to search

National and Kapodistrian University of Athens

Asymptotic Analysis of Outerplanar Graphs with Subgraph Obstructions

Abstract

dc:description

Σε αυτή την εργασία μελετάμε τεχνικές συνδυαστικής μοντελοποίησης καιασυμπτωτικής απαρίθμησης στο πλαίσιο της αναλυτικής συνδυαστικής. Ο οδηγός μας μέσα σε αυτή την πληθώρα τεχνικών είναι η απαρίθμηση κάποιων τύπων επίπεδων γραφημάτων, όταν εξαιρούμε συγκεκριμένα υπογραφήματα. Για την ακρίβεια, μελετάμε εξωεπίπεδα γραφήματα όταν ο περιορισμός είναι ο αποκλεισμός κύκλων συγκεκριμένου μήκους. Κατασκευάζουμε συνδυαστικές περιγραφές για τις δισυνεκτικές συνιστώσες που εξαιρούν τους κύκλους ώστε να αποκτήσουμε ασυμπτωτικά αποτελέσματα για τη γενική κλάση των εξωεπίπεδων γραφημάτων υπό περιορισμό. Οι προκλήσεις είναι συνδυαστικής αλλά και υπολογιστικής φύσης, καθώς οι περιγραφές γίνονται πιο περίπλοκες όταν το μήκος των κύκλων μεγαλώνει και οι γεννήτριες συναρτήσεις δίνονται σε έμμεση μορφή. Η συνδυαστική γλώσσα που χρησιμοποιείται είναι η λεγόμενη Συμβολική Μέθοδος που έρχεται μαζί με αντίστοιχες αναλυτικές τεχνικές.Επίσης μελετάμε παραμέτρους γενικών εξωεπίπεδων γραφημάτων, συγκεκριμένα τον αριθμό των τριγώνων και των τετραγώνων. Καταλήγουμε σε κανονικές οριακές κατανομές και εξάγουμε συγκεκριμένες σταθερές για την μέση τιμή και τη διασπορά.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Βελώνα Βασιλική

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1320908

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

Βελώνα Βασιλική. Asymptotic Analysis of Outerplanar Graphs with Subgraph Obstructions. 2016. https://pergamos.lib.uoa.gr/uoa/dl/object/1320908