Ισχυρές κλίκες σε γραφήματα
Φόρτωση...
Ημερομηνία
Συγγραφείς
Ζώνιος, Ελευθέριος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
αλγόριθμοι και πολυπλοκότητα σχετικών προβλημάτων
algorithms and complexity of related problems
algorithms and complexity of related problems
Περιγραφή
Ο κεντρικός στόχος της παρούσας διατριβής είναι η παρουσίαση και η ανάλυση σε βάθος έξι προβλημάτων που σχετίζονται με ισχυρές κλίκες σε διάφορες κλάσεις γραφημάτων. Μελετάμε την υπολογιστική πολυπλοκότητα των προβλημάτων αυτών που συναντώνται στην σύγχρονη βιβλιογραφία. Πιο συγκεκριμένα, η διατριβή αποτελείται από πέντε κεφάλαια. Στο πρώτο κεφάλαιο αναφέρονται εισαγωγικές έννοιες της θεωρίας γραφημάτων και ορισμοί σχετικοί με την έννοια της υπολογιστικής πολυπλοκότητας. Στο δεύτερο κεφάλαιο δίνεται η διατύπωση των έξι προβλημάτων, καθώς, και οι εφαρμογές τους σε άλλους κλάδους των μαθηματικών και της κοινωνίας. Το τρίτο κεφάλαιο περιέχει την ανάλυση της υπολογιστικής πολυπλοκότητας των πέντε εκ των έξι προβλημάτων σε ορισμένες κλάσεις γραφημάτων. Στο τέταρτο κεφάλαιο αναλύεται η υπολογιστική πολυπλοκότητα του τελευταίου προβλήματος στις κλάσεις γραφημάτων του τρίτου κεφαλαίου, συμπεριλαμβανομένου ενός αλγορίθμου που λύνει το πρόβλημα σε πολυωνυμικό χρόνο στην κλάση των cographs και την απόρριψη της εικασίας του Zaare-Nahandi μέσω αντιπαραδειγμάτων. Τέλος, στο πέμπτο κεφάλαιο παρουσιάζουμε τα συμπεράσματα αυτής της διατριβής.
The main goal of this study is the presentation and in-depth analysis of six problems related to strong cliques in various classes of graphs. We study the computational complexity of these problems encountered in the modern literature. More specifically, the study consists of five chapters. In the first chapter we introduce introductory concepts of graph theory and definitions related to the concept of computational complexity. In the second chapter, we give the formulation of the six problems related to strong cliques, as well as their applications in other branches of mathematics and society. The third chapter contains the analysis of the computational complexity of five of the six problems in certain graph classes. In the fourth chapter, we analyze the computational complexity of the last problem in the graph classes of the third chapter, including an algorithm that solves the problem in polynomial time in the class cographs, and we reject the conjecture of Zaare-Nahandi by giving some counterexamples. Finally, in the fifth chapter, we present the conclusions of this study.
The main goal of this study is the presentation and in-depth analysis of six problems related to strong cliques in various classes of graphs. We study the computational complexity of these problems encountered in the modern literature. More specifically, the study consists of five chapters. In the first chapter we introduce introductory concepts of graph theory and definitions related to the concept of computational complexity. In the second chapter, we give the formulation of the six problems related to strong cliques, as well as their applications in other branches of mathematics and society. The third chapter contains the analysis of the computational complexity of five of the six problems in certain graph classes. In the fourth chapter, we analyze the computational complexity of the last problem in the graph classes of the third chapter, including an algorithm that solves the problem in polynomial time in the class cographs, and we reject the conjecture of Zaare-Nahandi by giving some counterexamples. Finally, in the fifth chapter, we present the conclusions of this study.
Περιγραφή
Λέξεις-κλειδιά
Κλίκα, Αλγόριθμος, Πολυπλοκότητα, Γράφημα, Clique, Algorithm, Complexity, Localizable
Θεματική κατηγορία
Αλγόριθμοι
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Όνομα επιβλέποντος
Παπαδόπουλος, Χάρης
Εξεταστική επιτροπή
Παπαδόπουλος, Χάρης
Γεωργιάδης, Λουκάς
Παληός, Λεωνίδας
Γεωργιάδης, Λουκάς
Παληός, Λεωνίδας
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 83-89
Ονόματα συντελεστών
Αριθμός σελίδων
89 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States