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