Ένα από τα πιο σημαντικά προβλήματα σε γραφήματα είναι το ταίριασμα υπογραφημάτων (subgraph matching). Δοθέντος δύο γραφημάτων G1 και G2, το πρόβλημα αυτό αναζητά μία ένα ή περισσότερα ταιριάσματα του G2 μέσα στο G1. Ένα ταίριασμα είναι ένα υποσύνολο κορυφών και ακμών του G1 τέτοιο ώστε να υπάρχει μια 1-1 αντιστοιχία με τις κορυφές και τις ακμές του G2. Στόχος της διπλωματικής αυτής είναι να μελετήσει τεχνικές επίλυσης του προβλήματος αυτού που βασίζονται στην τοπική αναζήτηση με μεθόδους που βασίζονται στο hill-climbing.

Απαιτούμενες γνώσεις: Προγραμματισμός (π.χ. C ή Java), Αλγόριθμοι και Δομές Δεδομένων, Τεχνητή Νοημοσύνη (Προβλήματα Ικανοποίησης Περιορισμών).

Επιβλέπων Καθηγητής: Κώστας Στεργίου