δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
(EL)
Στην διατριβή αυτή ασχολούμαστε με προβλήματα σχετικά με το Αποτελεσματικό Κυρίαρχο σύνολο σε γραφήματα: Δοθέντος ενός γραφήματος G=(V,E), όπου V είναι το σύνολο των κορυφών και E το σύνολο των ακμών, μας ενδιαφέρει να βρούμε εκείνο το σύνολο κορυφών D με την ιδιότητα ότι κάθε κορυφή του γραφήματος G να κυριαρχείται από μία ακριβώς κορυφή του συνόλου D. Επικεντρωνόμαστε στους αλγορίθμους και στη πολυπλοκότητα του προβλήματος που υπάρχουν στην σύγχρονη βιβλιογραφία. Εστιάζουμε το ενδιαφέρον μας σε κλάσεις γραφημάτων όπου το πρόβλημα είτε παραμένει NP-δύσκολο είτε επιδέχεται πολυωνυμικό αλγόριθμο για την επιλυσή του. Παρουσιάζουμε αναγωγές για την δυσκολία του προβλήματος και ταυτόχρονα μελετάμε αλγορίθμους και τη γενικότερη μεθοδολογία που έχει αναπτυχθεί για την επιλυσή του. Κυρίως μας ενδιαφέρουν κλάσεις γραφημάτων που χαρακτηρίζονται από την απουσία επαγώμενου υπογραφήματος H, για δεδομένο γράφημα H.
(EL)
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)
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
(EL)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
