Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/29604Full metadata record
| DC Field | Value | Language |
|---|---|---|
| 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.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.secondaryTitle | αλγόριθμοι και πολυπλοκότητα | el |
| heal.classification | Γραφήματα (Μαθηματικά) | - |
| heal.dateAvailable | 2020-02-05T08:33:32Z | - |
| heal.language | el | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2019 | - |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 77-80 | 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.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Νούτσος, Δημήτριος | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 80 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΠΑΠΠΑ-ΖΩΗ ΠΑΝΑΓΙΩΤΑ 2019.pdf | 709.93 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
