Επιστημη

Πρόγραμμα "Επιστημονικές μελέτες"

Αποδοτικοι Αλγοριθμοι για Προβληματα Reachability και ΕπιλογηΣ Μονοπατιου και ΕφαρμογεΣ τουΣ

Τμημα Μηχανικων ΠληροφορικηΣ και Τηλεπικοινωνιων, Πανεπιστημιο ΔυτικηΣ ΜακεδονιαΣ

2010

Τα γραφήματα είναι μαθηματικές δομές που μοντελοποιούν πολλές σημαντικές οντότητες, όπως ο παγκόσμιος ιστός, μεταφορικά, επικοινωνιακά και κοινωνικά δίκτυα, βάσεις δεδομένων και βιολογικά συστήματα.

Σκοπός της παρούσας μελέτης ήταν η σχεδίαση αποδοτικών αλγόριθμων για μια συλλογή προβλημάτων που σχετίζονται με τη Συνδετικότητα και την Επιλογή Μονοπατιών σε γραφήματα. Για τέτοιου είδους προβλήματα μας δίνεται ένα γράφημα εισόδου και επιθυμούμε να απαντούμε με αποδοτικό τρόπο ερωτήματα για το εάν δύο κορυφές του συνδέονται με κάποιο μονοπάτι ή να υπολογίζουμε μονοπάτια που συνδέουν συγκεκριμένες κορυφές και ταυτόχρονα ικανοποιούν καθορισμένες απαιτήσεις.

Αλγοριθμικά προβλήματα αυτού του τύπου έχουν πολυάριθμες εφαρμογές που περιλαμβάνουν τη δρομολόγηση σε δίκτυα, τη γεωγραφική πλοήγηση και τα συστήματα αναπαράστασης γνώσης. Συγκεκριμένα, στο πρόγραμμα αυτό εξερευνήσαμε τους ακόλουθους τύπους προβλημάτων:

Από Κοινού Συνδετικότητα: Είναι μια φυσική επέκταση του τυπικού προβλήματος Συνδετικότητας για μια συλλογή γραφημάτων G. H G υφίσταται επεξεργασία έτσι ώστε να είμαστε σε θέση να αναφέρουμε σε σύντομο χρόνο το σύνολο των κορυφών για τις οποίες υπάρχει μονοπάτι προς μια δεδομένη κορυφή σε όλα τα γραφήματα της G.

Υπολογισμός Μη Τεμνόμενων Μονοπατιών: Ο στόχος μας είναι να υπολογίσουμε ένα ζεύγος μη τεμνόμενων μονοπατιών από μια δεδομένη αφετηριακή κορυφή προς κάθε άλλη κορυφή ή προς μια συγκεκριμένη καταληκτική κορυφή.

Αναπτύξαμε αλγοριθμικές τεχνικές και παρουσιάσαμε αποδοτικούς αλγόριθμους για προβλήματα των παραπάνω τύπων. Επιπλέον, αναζητήσαμε νέες εφαρμογές των τεχνικών και των αλγορίθμων μας.

Τελική αναφορά (στα Αγγλικά)

ΦΩΤΟΓΡΑΦΙΕΣ

Συντονιστής:

Γεωργιάδης Λουκάς, Επίκουρος Καθηγητής, Τμήμα Μηχανικών Πληροφορικής και Τηλεπικοινωνιών, Πανεπιστήμιο Δυτικής Μακεδονίας

Μέλη Ομάδας:

Γαλάνη Αλεξάνδρα, Ειδικό και Εργαστηριακό Διδακτικό Προσωπικό, Τμήμα Μηχανικών Πληροφορικής και Τηλεπικοινωνιών, Πανεπιστήμιο Δυτικής Μακεδονίας

Νικολόπουλος Σταύρος, Καθηγητής, Τμήμα Πληροφορικής, Πανεπιστήμιο Ιωαννίνων

Παληός Λεωνίδας, Αναπληρωτής Καθηγητής, Τμήμα Πληροφορικής, Πανεπιστήμιο Ιωαννίνων

Καραμανλή & Ληγερής

50100 Κοζάνη

Τηλ.: 24610 56 500

Φαξ.: 2461056 501

icte@uowm.gr

icte.uowm.gr/

menuShadow