National and Kapodistrian University of Athens
An alternative proof for the NP-completeness of the Grid Subgraph problem
Abstract
dc:descriptionΣτον τομέα της Γραφικής Αναπαράστασης Γραφημάτων υπάρχει μεγάλο ενδιαφέρον για αποτελέσματα σχετικά με την εμβάπτιση ενός δοθέντος γραφήματος πάνω σε μία σχάρα, κυρίως λόγω των εφαρμογών στο σχεδιασμό κυκλωμάτων VLSI. Πιο συγκεκριμένα, το ερώτημα αν ένα γράφημα επιδέχεται εμβάπτιση μοναδιαίου μήκους, δηλαδή μια αντιστοίχιση των κορυφών και των ακμών του γραφήματος σε κορυφές και ακμές μιας αρκετά μεγάλης σχάρας, ταυτίζεται με το ερώτημα αν το γράφημα είναι υπογράφημα της συγκεκριμένης σχάρας. Θεωρούμε το πρόβλημα Υπογράφημα Σχάρας, στο οποίο δοθέντος ενός επίπεδου (όχι απαραίτητα συνεκτικού) γραφήματος G, καλούμαστε να αποφανθούμε αν το G είναι ισόμορφο με κάποιο υπογράφημα μιας αρκετά μεγάλης σχάρας. Αποδεικνύουμε ότι το πρόβλημα αυτό είναι NP-πλήρες χρησιμοποιώντας απλά και διαισθητικά για να ανάγουμε σε αυτό μία παραλλαγή του προβλήματος SAT (ικανοποίησης λογικής φόρμουλας). Προς αυτό αποδεικνύουμε ότι και η ειδική περίπτωση του προβλήματος στην οποία το μέγεθος της σχάρας είναι προκαθορισμένο, γνωστό και ως το πρόβλημα Υπογράφημα (k *k)-Σχάρας, είναι επίσης NP-πλήρες.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Χατζηδημητρίου Δημήτριος
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1320877