Αποτελεσματικό κυρίαρχο σύνολο σε γραφήματα
Φόρτωση...
Ημερομηνία
Συγγραφείς
Παππά-Ζώη, Παναγιώτα
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
αλγόριθμοι και πολυπλοκότητα
Περιγραφή
Στην διατριβή αυτή ασχολούμαστε με προβλήματα σχετικά με το Αποτελεσματικό Κυρίαρχο σύνολο σε γραφήματα: Δοθέντος ενός γραφήματος G=(V,E), όπου V είναι το σύνολο των κορυφών και E το σύνολο των ακμών, μας ενδιαφέρει να βρούμε εκείνο το σύνολο κορυφών D με την ιδιότητα ότι κάθε κορυφή του γραφήματος G να κυριαρχείται από μία ακριβώς κορυφή του συνόλου D. Επικεντρωνόμαστε στους αλγορίθμους και στη πολυπλοκότητα του προβλήματος που υπάρχουν στην σύγχρονη βιβλιογραφία. Εστιάζουμε το ενδιαφέρον μας σε κλάσεις γραφημάτων όπου το πρόβλημα είτε παραμένει NP-δύσκολο είτε επιδέχεται πολυωνυμικό αλγόριθμο για την επιλυσή του. Παρουσιάζουμε αναγωγές για την δυσκολία του προβλήματος και ταυτόχρονα μελετάμε αλγορίθμους και τη γενικότερη μεθοδολογία που έχει αναπτυχθεί για την επιλυσή του. Κυρίως μας ενδιαφέρουν κλάσεις γραφημάτων που χαρακτηρίζονται από την απουσία επαγώμενου υπογραφήματος H, για δεδομένο γράφημα H.
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.
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.
Περιγραφή
Λέξεις-κλειδιά
Γραφήματα (Μαθηματικά), Graphs
Θεματική κατηγορία
Γραφήματα (Μαθηματικά)
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Όνομα επιβλέποντος
Παπαδόπουλος, Χάρης
Εξεταστική επιτροπή
Παπαδόπουλος, Χάρης
Νούτσος, Δημήτριος
Γεωργιάδης, Λουκάς
Νούτσος, Δημήτριος
Γεωργιάδης, Λουκάς
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 77-80
Ονόματα συντελεστών
Αριθμός σελίδων
80 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States