Εύρεση μη-συνεκτικού διαχωριστή σε γραφήματα
Φόρτωση...
Ημερομηνία
Συγγραφείς
Κιαφζέζι, Ιωάννα
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Ο κεντρικός στόχος της παρούσης διατριβής είναι η παρουσίαση και ανάλυση σε ϐάθος του προβλήματος της εύρεσης ενός μη συνεκτικού διαχωριστή σε συνεκτικά γραφήματα: δοθέντος ενός συνεκτικού γραφήματος G, ϑέλουμε να υπολογίσουμε ένα υποσύνολο κορυφών S (το οποίο καλείται διαχωριστής) ,τέτοιο ώστε τα δύογραφήματα G\S και G [S] να είναι μη-συνεκτικά γραφήματα. Με άλ λα λόγια το πρόβλημα αποσκοπεί στην εύρεση ενός μη-συνεκτικού διαχωριστή. Μελετάμε την υπολογιστική πολυπλοκότητα του προβλήματος που συναντάται στη σύγχρονη ϐιβλιογραφία. Πιοσυγκεκριμένα, η διατριβή αποτελείται από πέντε κεφάλαια. Στο πρώτο κεφάλαιο αναφέρονται εισαγωγικές έννοιες της ϑεωρίας γραφημάτων καθώς και η έννοια της υπολογιστικής πολυπλοκότητας.Το δεύτερο κεφάλαιο είναι αφιερωμένο στον ορισμό του προβλήματος του μη συνεκτικού διαχωριστή και σε προβλήματα ισοδύναμα με αυτό.Στο τρίτο κεφάλαιο αναλύεται η υπολογιστική πολυπλοκότητα του προβλήματος στις περιπτώσεις όπου το γράφημα έχει διάμετρο ίση με δύο και διάμετρο διάφορη του δύο. Στο επόμενο κεφάλαιο αναφέρουμε τις κλάσεις γραφημάτων όπου το πρόβλημα ε πιδέχεται πολυωνυμική λύση, εστιάζοντας στα H-free γραφήματα.Στο πέμπτο και τελευταίο κεφάλαιο παρουσιάζουμε τα συμπεράσματα αυτής της διατριβής και επίσης επεκτείνουμε τα ήδη γνωστά πολυωνυμικά αποτελέσματα, σχεδιάζο ντας τον πρώτο πολυωνυμικό αλγόριθμο για την κλάση των distance-hereditary γραφημάτων.
The principal aim of this thesis is to present an extended analysis of the problem of finding a disconnected cut within a connected graph: given a connected graph G, our task is to find a set S of vertices such that both graphs G\S and G [S] are disconnected. Therefore, the goal of the problem is to find a disconnected cut of a given connected graph .We study the computational complexity of disconnected cut problem, which can be found in the modern literature. More specifically, the thesis consists of five chapters. In the first chapter mentioned some basic concepts in graph theory and the definition of computational complexity .The second chapter is devoted to the definition of disconnected cut problem and some polynomially equivalent problems .In the third chapter we analyze the computational complexity of disconnected cut to graphs of diameter2 and to graphs of diameter 1 or at least 3.Inthenext chapter we mention several graph classes where the disconnected cut problem has polynomial-time algorithms. We are focused on H-free graphs. In the fifth and last chapter we present the conclusions of this thesis and also extend the already known polynomial results, constructing the first polynomial algorithm for distance-hereditary graphs.
The principal aim of this thesis is to present an extended analysis of the problem of finding a disconnected cut within a connected graph: given a connected graph G, our task is to find a set S of vertices such that both graphs G\S and G [S] are disconnected. Therefore, the goal of the problem is to find a disconnected cut of a given connected graph .We study the computational complexity of disconnected cut problem, which can be found in the modern literature. More specifically, the thesis consists of five chapters. In the first chapter mentioned some basic concepts in graph theory and the definition of computational complexity .The second chapter is devoted to the definition of disconnected cut problem and some polynomially equivalent problems .In the third chapter we analyze the computational complexity of disconnected cut to graphs of diameter2 and to graphs of diameter 1 or at least 3.Inthenext chapter we mention several graph classes where the disconnected cut problem has polynomial-time algorithms. We are focused on H-free graphs. In the fifth and last chapter we present the conclusions of this thesis and also extend the already known polynomial results, constructing the first polynomial algorithm for distance-hereditary graphs.
Περιγραφή
Λέξεις-κλειδιά
Γραφήματα (Μαθηματικά), Connected graph
Θεματική κατηγορία
Γραφήματα (Μαθηματικά)
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Όνομα επιβλέποντος
Παπαδόπουλος, Χάρης
Εξεταστική επιτροπή
Παπαδόπουλος, Χάρης
Γεωργιάδης, Λουκάς
Νούτσος, Δημήτριος
Γεωργιάδης, Λουκάς
Νούτσος, Δημήτριος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 99-100
Ονόματα συντελεστών
Αριθμός σελίδων
100 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States