Back to search

National and Kapodistrian University of Athens

On the relation between treewidth and toughness

Abstract

dc:description

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Γερακιός Κωνσταντίνος

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1321312

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

Γερακιός Κωνσταντίνος. On the relation between treewidth and toughness. 2012. https://pergamos.lib.uoa.gr/uoa/dl/object/1321312