Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής

• Main Author: Ραπτόπουλος, Χριστόφορος
• Other Authors: Νικολετσέας, Σωτήρης
• Published: 2007
• Subjects: Τυχαίο Γράφημα Τομής; Πιθανοτικός αλγόριθμος; Ανεξάρτητο σύνολο κορυφών; Random Intersection Graph; Randomized algorithm; Independent set; 005.1

Στη διπλωματική αυτή εργασία ορίζουμε δυο νέα μοντέλα τυχαίων γραφημάτων τομής ετικετών και εξετάζονται ως προς ορισμένες σημαντικές γραφοθεωρητικές ιδιότητές τους. Ένα τυχαίο γράφημα τομής ετικετών παράγεται αντιστοιχώντας σε κάθε κορυφή ένα \\\\emph{τυχαίο} υποσύνολο ενός πεπερασμένου) σύμπαντος $...