Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/31460Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Πέτρου, Μαριάννα | el |
| dc.date.accessioned | 2021-11-08T08:28:20Z | - |
| dc.date.available | 2021-11-08T08:28:20Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/31460 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.11281 | - |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Ελαχιστοτικοί διαχωριστές | el |
| dc.subject | FPT Αλγόριθμοι | el |
| dc.subject | Πολυμερείς διαχωριστές | el |
| dc.subject | Σημαντικοί διαχωριστές | el |
| dc.subject | Minimal separators | en |
| dc.subject | FPT algorithms | en |
| dc.subject | Multiway separators | en |
| dc.subject | Important separators | en |
| dc.title | Ελαχιστοτικοί διαχωριστές | el |
| dc.title | Minimal separators | en |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.secondaryTitle | αλγόριθμοι και σχετικά προβλήματα | el |
| heal.secondaryTitle | algorithms and related problems | en |
| heal.classification | Ελαχιστοτικοί διαχωριστές | - |
| heal.dateAvailable | 2021-11-08T08:29:20Z | - |
| heal.language | el | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2021 | - |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 101-105 | el |
| heal.abstract | Η παρούσα διατριβή έχει ως στόχο την αλγοριθμική μελέτη των ελαχιστοτικών διαχωριστών σε γραφήματα. ΄Ενα σύνολο κορυφών ενός συνεκτικού γραφήματος καλείται ελαχιστοτικός διαχωριστής αν η αφαίρεση του συνόλου οδηγεί σε μησυνεκτικό γράφημα και κανένα αυστηρό υποσύνολό του δεν έχει την ίδια ιδιότητα. Είναι γνωστό ότι ένα γράφημα μπορεί να έχει πλήθος ελαχιστοτικών διαχωριστών που να είναι εκθετικό ως προς το μέγεθος του γραφήματος, ενώ παράλληλα ένας ελάχιστος (ως προς το μέγεθος) διαχωριστής μπορεί να υπολογιστεί σε πολυωνυμικό χρόνο μέσα από τη θεωρία μεγίστων ροών. Εξετάζουμε την υπολογιστική πολυπλοκότητα ορισμένων προβλημάτων της αλγοριθμικής θεωρίας γραφημάτων που σχετίζονται με τους ελαχιστοτικούς διαχωριστές. Στο πρώτο κεφάλαιο αναφέρουμε εισαγωγικές έννοιες της θεωρίας γραφημάτων και της υπολογιστικής πολυπλοκότητας. Στη συνέχεια, στο δεύτερο κεφάλαιο μελετάμε ένα γνωστό αλγόριθμο που απαριθμεί τους ελαχιστοτικούς διαχωριστές ενός γραφήματος καθώς και το πλήθος των ελαχιστοτικών διαχωριστών που περιέχει, του οποίου ο χρόνος είναι πολυωνυμικός ως προς το μέγεθος του γραφήματος. Στο τρίτο κεφάλαιο εξετάζουμε κλάσεις γραφημάτων που παρουσιάζουν πολυωνυμικό πλήθος ελαχιστοτικών διαχωριστών και επικεντρώνουμε το ενδιαφέρον μας σε γραφήματα που χαρακτηρίζονται από απαγορευμένα επαγόμενα υπογραφήματα το πολύ τεσσάρων κορυφών. Ακολούθως, στο τέταρτο και πέμπτο κεφάλαιο μελετάμε την πολυπλοκότητα δύο σχετικών προβλημάτων που αποσκοπούν στην εύρεση του μέγιστου και του πολυμερούς ελαχιστοτικού διαχωριστή αντίστοιχα. Πιο συγκεκριμένα, δείχνουμε γνωστές αναγωγές NP-πληρότητας για την εύρεση ενός μέγιστου ελαχιστοτικού διαχωριστή σε επίπεδα διμερή γραφήματα, σε συμπληρώματα διμερών γραφημάτων και σε γραμμικά γραφήματα, ενώ για το ίδιο πρόβλημα δείχνουμε ότι επιδέχεται παραμετρική πολυπλοκότητα (FPT) ως προς το μέγεθος της λύσης. Για την εύρεση ενός πολυμερούς ελαχιστοτικού διαχωριστή, στο πέμπτο κεφάλαιο, δείχνουμε γνωστή αναγωγή για την NP-δυσκολία του προβλήματος και παρουσιάζουμε γνωστό αλγόριθμο που τρέχει σε πολυωνυμικό χρόνο για γραφήματα με φραγμένο δεντροπλάτος. Επίσης, στο έκτο κεφάλαιο εξετάζουμε την αντίστοιχη έννοια των ελαχιστοτικών διαχωριστών ως προς τις ακμές του γραφήματος και συγκεκριμένα μελετάμε την έννοια των σημαντικών διαχωριστών. Παρουσιάζουμε ακόμη, ορισμένα πεδία εφαρμογής των σημαντικών διαχωριστών σε σχέση με άλλα γνωστά προβλήματα αποκοπής. Τέλος, κλείνουμε τη διατριβή με το έβδομο κεφάλαιο παρουσιάζοντας συγκεντρωτικά τα αποτελέσματα των προηγούμενων κεφαλαίων. | el |
| heal.abstract | The present thesis aims the algorithmic study of minimal separators in graphs. A set of vertices of a connected graph is called a minimal separator if subtracting the set results in a disconnected graph and no proper subset of it has the same property. It is known that a graph can have a number of minimal separators that is exponential, while at the same time a minimum separator can be calculated in polynomial time through maximum flow theory. We consider the computational complexity of some algorithmic graph theory problems related to minimal separators. Firstly, we introduce basic concepts and definitions of graph theory and computational complexity. Next, in the second chapter we study a known algorithm, whose time is polynomial, that lists the minimum separators of a graph and the number of minimal separators it contains as well. In the third chapter we examine graph classes that present a polynomial number of minimal separators and focus on graphs characterized by forbidden induced subgraphs of at most four vertices. Furthermore, in the fourth and fifth chapter, we study the complexity of two related problems aimed at finding the maximum and the multiway separator, respectively. More specifically, we show known NP-complete reductions in order to find a maximum minimal separator in planar bipartite graphs, in co-bipartite graphs and in line graphs, while for the same problem we show that it is susceptible to parametric complexity FPT in terms of solution size. To find a minimal multiway separator, in the fifth chapter, we show a known NP-hard reduction for the problem and present a well-known algorithm that runs in polynomial time for graphs with bounded treewidth. Also, in the sixth chapter we examine the corresponding concept of the minimal separators with respect to the edges of the graph and in particular we study important separators. We present some areas of application of important separators in relation to other known cutting problems. We conclude the thesis with the seventh chapter presenting summary results of the previous chapters. | en |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 105 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΠΕΤΡΟΥ ΜΑΡΙΑΝΝΑ 2021.pdf | 2.62 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
