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

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

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