Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2016-10-21
Συγγραφέας:
Χατζηδημητρίου Δημήτριος
Στοιχεία επιβλεπόντων καθηγητών:
Δημήτριος Μ. Θηλυκός Καθηγητής
Πρωτότυπος Τίτλος:
An alternative proof for the NP-completeness of the Grid Subgraph problem
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Μια εναλλακτική απόδειξη της NP-πληρότητας του προβλήματος "Υπογράφημα Σχάρας"
Περίληψη:
Στον τομέα της Γραφικής Αναπαράστασης Γραφημάτων υπάρχει μεγάλο ενδιαφέρον για
αποτελέσματα σχετικά με την εμβάπτιση ενός δοθέντος γραφήματος πάνω σε μία
σχάρα, κυρίως λόγω των εφαρμογών στο σχεδιασμό κυκλωμάτων VLSI. Πιο
συγκεκριμένα, το ερώτημα αν ένα γράφημα επιδέχεται εμβάπτιση μοναδιαίου μήκους,
δηλαδή μια αντιστοίχιση των κορυφών και των ακμών του γραφήματος σε κορυφές και
ακμές μιας αρκετά μεγάλης σχάρας, ταυτίζεται με το ερώτημα αν το γράφημα είναι
υπογράφημα της συγκεκριμένης σχάρας. Θεωρούμε το πρόβλημα Υπογράφημα Σχάρας,
στο οποίο δοθέντος ενός επίπεδου (όχι απαραίτητα συνεκτικού) γραφήματος G,
καλούμαστε να αποφανθούμε αν το G είναι ισόμορφο με κάποιο υπογράφημα μιας
αρκετά μεγάλης σχάρας. Αποδεικνύουμε ότι το πρόβλημα αυτό είναι NP-πλήρες
χρησιμοποιώντας απλά και διαισθητικά για να ανάγουμε σε αυτό μία παραλλαγή του
προβλήματος SAT (ικανοποίησης λογικής φόρμουλας). Προς αυτό αποδεικνύουμε ότι
και η ειδική περίπτωση του προβλήματος στην οποία το μέγεθος της σχάρας είναι
προκαθορισμένο, γνωστό και ως το πρόβλημα Υπογράφημα (k*k)-Σχάρας, είναι
επίσης NP-πλήρες.
Λέξεις-κλειδιά:
Εμβάπτιση γραφημάτων, Ορθογώνια εμβάπτιση, Εμβάπτιση μοναδιαίου μήκους, Σχεδιασμός VLSI, NP-πληρότητα
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
17
