Από την Θεωρία Γραφημάτων στα Μητροειδή: Αλγοριθμικές Συνέπειες και Εφαρμογές

Abstract: 

Η πράξη: ΘΑΛΗΣ – ΑΡΙΣΤΟΤΕΛΕΙΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΘΕΣΣΑΛΟΝΙΚΗΣ - "Από την Θεωρία Γραφημάτων στα Μητροειδή: Αλγοριθμικά Θέματα και Εφαρμογές" θα εκτελεστεί ως εξής: Υποέργο 1: «Από την Θεωρία Γραφημάτων στα Μητροειδή: Αλγοριθμικά Θέματα και Εφαρμογές».

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

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

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

Δράσεις:

  1. Θεωρία αποσύνθεσης για GF(2)-αναπαραστήσιμα προσημασμένα-γραφικά μητροειδή.
  2. Θεωρία αποσύνθεσης για GF(4)-αναπαραστήσιμα προσημασμένα-γραφικά μητροειδή.
  3. Αλγόριθμοι αναγνώρισης προσημασμένων-γραφικών μητροειδών.
  4. Δομή κοινοτήτων σε γραφικά και προσημασμένα-γραφικά μητροειδή.
  5. Δυναμικός προγραμματισμός σε γραφήματα:ανάπτυξη και ανάλυση.
  6. Αλγοριθμικές τεχνικής θεωρίας ελασσόνων γραφημάτων.
  7. Εφαρμογές της "τεχνικής της ασήμαντης κορυφής".
  8. Αλγοριθμικές και συνδυαστικές επεκτάσεις της θεωρίας ελασσόνων γραφημάτων.
  9. Πολύτοπα τομής πολυμητροειδών.
  10. Αλγόριθμοι βελτιστοποίησης σε πολύτοπα τομής πολυμητροειδών.
  11. Αποσύνθεση πολυτόπων και ελάσσονα πολύτοπα.
  12. Εφαρμογές αποσύνθεσης πολυτόπων και τομών πολυμητροειδών.
  13. Ανασκόπηση βιβλιογραφίας.
  14. Πολυεδρική ανάλυση.
  15. Ανάπτυξη και υλοποίηση αλγοριθμικών μεθόδων επίλυσης προβλημάτων διακριτής βελτιστοποίησης.
  16. Εσωτερική Αξιολόγηση.
  17. Δράση Δημοσιότητας - Δημιουργία Ιστοσελίδας.

ΠΛΗΡΟΦΟΡΙΕΣ ΕΡΓΟΥ

Ακρωνύμιο:
GTM
Επιστημονικός Υπεύθυνος:
Πιτσούλης Λεωνίδας
Επιστημ. Υπεύθυνος 2ης Ερευνητικής Ομάδας:
Θηλυκός Δημήτριος
Επιστημ. Υπεύθυνος 3ης Ερευνητικής Ομάδας:
Μούρτος Γιάννης
Επιστημ. Υπεύθυνος 4ης Ερευνητικής Ομάδας:
Μάγος Δημήτριος

ΣΤΟΙΧΕΙΑ ΕΡΓΟΥ

Κωδικός Έργου:
617
Mis:
379437
Διάρκεια (μήνες):
43
Προϋπολογισμός:
599 955.00
Διαύγεια:
ΑΔΑ: Β4Λ59-ΦΔΞ

ΒΙΒΛΙΟΘΗΚΗ ΕΡΓΟΥ

ΝΕΑ