Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Χατζηδημητρίου Δημήτριος. An alternative proof for the NP-completeness of the Grid Subgraph problem. 2016. https://pergamos.lib.uoa.gr/uoa/dl/object/1320877