Ταίριασμα υπογραφημάτων με τοπική αναζήτηση

14-10-2013


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

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

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