Αποτελεσματικό κυρίαρχο σύνολο σε γραφήματα
| dc.contributor.author | Παππά-Ζώη, Παναγιώτα | el |
| dc.date.accessioned | 2020-02-05T08:32:32Z | |
| dc.date.available | 2020-02-05T08:32:32Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/29604 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.9606 | |
| 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 | Graphs | en |
| dc.title | Αποτελεσματικό κυρίαρχο σύνολο σε γραφήματα | el |
| heal.abstract | Στην διατριβή αυτή ασχολούμαστε με προβλήματα σχετικά με το Αποτελεσματικό Κυρίαρχο σύνολο σε γραφήματα: Δοθέντος ενός γραφήματος G=(V,E), όπου V είναι το σύνολο των κορυφών και E το σύνολο των ακμών, μας ενδιαφέρει να βρούμε εκείνο το σύνολο κορυφών D με την ιδιότητα ότι κάθε κορυφή του γραφήματος G να κυριαρχείται από μία ακριβώς κορυφή του συνόλου D. Επικεντρωνόμαστε στους αλγορίθμους και στη πολυπλοκότητα του προβλήματος που υπάρχουν στην σύγχρονη βιβλιογραφία. Εστιάζουμε το ενδιαφέρον μας σε κλάσεις γραφημάτων όπου το πρόβλημα είτε παραμένει NP-δύσκολο είτε επιδέχεται πολυωνυμικό αλγόριθμο για την επιλυσή του. Παρουσιάζουμε αναγωγές για την δυσκολία του προβλήματος και ταυτόχρονα μελετάμε αλγορίθμους και τη γενικότερη μεθοδολογία που έχει αναπτυχθεί για την επιλυσή του. Κυρίως μας ενδιαφέρουν κλάσεις γραφημάτων που χαρακτηρίζονται από την απουσία επαγώμενου υπογραφήματος H, για δεδομένο γράφημα H. | el |
| heal.abstract | In this dissertation we deal with problems related to the efficient domination set in graphs: Given a graph G=(V,E), where V is the set of vertices and E is the set of edges, we are interested in finding that set of vertices D of the graph G with the property that every vertex of the graph G is dominated by exactly one vertex of the set D. We concentrate on algorithms and the complexity of the problem that can be found in the modern literature. Our interest is focused on classes of graphs where the problem remains NP-hard or admits a polynomial algorithm for its solution. We present reductions for the difficulty of the problem and simultaneously study algorithms and the general methodology that have been developed for its solution. We are mainly interested in classes of graphs that are characterised by the absence of an induced subgraph H, for every given graph H. | en |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 77-80 | el |
| heal.classification | Γραφήματα (Μαθηματικά) | |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Νούτσος, Δημήτριος | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.dateAvailable | 2020-02-05T08:33:32Z | |
| heal.fullTextAvailability | true | |
| heal.language | el | |
| heal.numberOfPages | 80 σ. | |
| heal.publicationDate | 2019 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.secondaryTitle | αλγόριθμοι και πολυπλοκότητα | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΠΑΠΠΑ-ΖΩΗ ΠΑΝΑΓΙΩΤΑ 2019.pdf
- Μέγεθος:
- 709.93 KB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: