Αλγόριθμοι και πολυπλοκότητα της ισχυρής τριαδικής κλειστότητας σε κλάσεις γραφημάτων
Φόρτωση...
Ημερομηνία
Συγγραφείς
Κωνσταντινίδης, Αθανάσιος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Στα κοινωνικά δίκτυα η Ισχυρη Τριαδικη κλειστοτητα είναι µία ανάθεση στις ακµές µε ισχυρές ή ασθενείς επιγραφές, τέτοια ώστε για δύο οποιεσδήποτε κορυ- φές που έχουν κοινό γείτονα µε ισχυρή ακµή να είναι γειτονικές. Το πρόβληµα της
µεγιστοποίησης των ισχυρών ακµών, οι οποίες ικανοποιούν την ισχυρή τριαδική κλειστότητα, έχει πρόσφατα αποδειχτεί ότι είναι NP-πλήρες σε γενικά γραφήµατα.
Στην παρούσα διατριβή γίνεται µελέτη σε κλάσεις γραφηµάτων, για τις οποίες το πρόβληµα χαρακτηρίζεται είτε µε πολυωνυµική λύση είτε παραµένει NP-πλήρες. 6είχνουµε ότι το πρόβληµα δέχεται πολυωνυµικό σε χρόνο αλγόριθµο σε δύο ανεξάρτητες κλάσεις γραφηµάτων των proper interval και των trivially-perfect, καθώς και στις κλάσεις των bipartite, co-bipartite και threshold γραφηµάτων. Για να έχουµε µια πιο κατηγοριοποιηµένη και ολοκληρωµένη αντίληψη των α- ποτελεσµάτων µας, δείχνουµε ότι το πρόβληµα παραµένει NP-πλήρες στα split γραφήµατα, και ακολούθως στα chordal γραφήµατα. Εποµένως, µέσα από την διατριβή αυτή συµβάλουµε να οριστούν τα πρώτα διαχωριστικά όρια µεταξύ των κλάσεων γραφηµάτων, όπου σε κάποιες κλάσεις το πρόβληµα λύνεται σε πολυω- νυµικό χρόνο ενώ σε άλλες κλάσεις το πρόβληµα παραµένει NP-πλήρες.
In social networks the Strong Triadic Closure is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. In this thesis we initiate the study of graph classes for which the problem is either polynomially solvable or remains NP-complete. We show that the problem admits a polynomialtime algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs, as well as, on classes of bipartite graphs, cobipartite graphs and threshold graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus in this thesis we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete.
In social networks the Strong Triadic Closure is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. In this thesis we initiate the study of graph classes for which the problem is either polynomially solvable or remains NP-complete. We show that the problem admits a polynomialtime algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs, as well as, on classes of bipartite graphs, cobipartite graphs and threshold graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus in this thesis we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete.
Περιγραφή
Λέξεις-κλειδιά
Γραφήματα, Ισχυρή τριαδική κλειστότητα
Θεματική κατηγορία
Αλγόριθμοι, Γραφήματα (Μαθηματικά)
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Όνομα επιβλέποντος
Παπαδόπουλος, Χάρης
Εξεταστική επιτροπή
Παπαδόπουλος, Χάρης
Νικολόπουλος, Σταύρος
Γλυνός, Νικόλαος
Νικολόπουλος, Σταύρος
Γλυνός, Νικόλαος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία : σ. 49-51
Ονόματα συντελεστών
Αριθμός σελίδων
51 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: An error occurred on the license name.