{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321312"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321312","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"On the relation between treewidth and toughness","abstract":"Τα προβλήματα υπολογισμού του δενδροπλάτους και της σκληρότητας ενός γραφήματος είναι γνωστά NP-hard προβλήματα. Το δενδροπλάτος ειναι ένα μέτρο συνεκτικότητας των γραφημάτων, καθώς και ένα μέτρο αποδοτικού υπολογισμού για γνωστά NP-δύσκολα προβλήματα ορισμένα σε γραφήματα. Η σκληρότητα από την άλλη, είναι ένα μέτρο ακυκλικότητας σε γραφήματα καθώς και μία παράμετρος ένδειξης της ύπαρξης κυκλικών δομών σε αυτά. Στην παρούσα διπλωματική εργασία, συσχετίζουμε αυτές τις δύο παραμέτρους ορισμένες σε γραφήματα, δίνοντας μερικά άνω φράγματα της σκληρότητας ως συνάρτηση του δενδροπλάτους και αιτιολογούμε ότι δεν υπάρχει ανάλογο κάτω φράγμα.","abstract_html":"Τα προβλήματα υπολογισμού του δενδροπλάτους και της σκληρότητας ενός γραφήματος είναι γνωστά NP-hard προβλήματα. Το δενδροπλάτος ειναι ένα μέτρο συνεκτικότητας των γραφημάτων, καθώς και ένα μέτρο αποδοτικού υπολογισμού για γνωστά NP-δύσκολα προβλήματα ορισμένα σε γραφήματα. Η σκληρότητα από την άλλη, είναι ένα μέτρο ακυκλικότητας σε γραφήματα καθώς και μία παράμετρος ένδειξης της ύπαρξης κυκλικών δομών σε αυτά. Στην παρούσα διπλωματική εργασία, συσχετίζουμε αυτές τις δύο παραμέτρους ορισμένες σε γραφήματα, δίνοντας μερικά άνω φράγματα της σκληρότητας ως συνάρτηση του δενδροπλάτους και αιτιολογούμε ότι δεν υπάρχει ανάλογο κάτω φράγμα.","abstract_has_math":false,"creators":["Γερακιός Κωνσταντίνος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-11-19T05:26:41Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321312"],"render_values":[{"text":"uoadl:1321312","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321312","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321312","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1321312","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Γερακιός Κωνσταντίνος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321312","https://pergamos.lib.uoa.gr/uoa/dl/object/1321312"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Τα προβλήματα υπολογισμού του δενδροπλάτους και της σκληρότητας ενός γραφήματος είναι γνωστά NP-hard προβλήματα. Το δενδροπλάτος ειναι ένα μέτρο συνεκτικότητας των γραφημάτων, καθώς και ένα μέτρο αποδοτικού υπολογισμού για γνωστά NP-δύσκολα προβλήματα ορισμένα σε γραφήματα. Η σκληρότητα από την άλλη, είναι ένα μέτρο ακυκλικότητας σε γραφήματα καθώς και μία παράμετρος ένδειξης της ύπαρξης κυκλικών δομών σε αυτά. Στην παρούσα διπλωματική εργασία, συσχετίζουμε αυτές τις δύο παραμέτρους ορισμένες σε γραφήματα, δίνοντας μερικά άνω φράγματα της σκληρότητας ως συνάρτηση του δενδροπλάτους και αιτιολογούμε ότι δεν υπάρχει ανάλογο κάτω φράγμα.","The problems of computing the treewidth and the toughness of a graph are well-known NP-hard problems. Treewidth is a measure of connectivity in graphs as well as a measure of efficient computing for well-known NP-hard problems defined in graphs. Tougness on the other hand is a measure of acyclicity of a graph as well as an indicator parameter for the existence of cyclic structures in graphs. In this Master's thesis, we relate these two graph paramers, giving some upper bounds on toughness as a function of treewidth and justify that there does not exist a similar lower bound."]},{"key":"dc:title","label":"Title","values":["On the relation between treewidth and toughness"]}]}],"canonical_facts":{"dc:creator":["Γερακιός Κωνσταντίνος"],"dc:date":["2012"],"dc:description":["Τα προβλήματα υπολογισμού του δενδροπλάτους και της σκληρότητας ενός γραφήματος είναι γνωστά NP-hard προβλήματα. Το δενδροπλάτος ειναι ένα μέτρο συνεκτικότητας των γραφημάτων, καθώς και ένα μέτρο αποδοτικού υπολογισμού για γνωστά NP-δύσκολα προβλήματα ορισμένα σε γραφήματα. Η σκληρότητα από την άλλη, είναι ένα μέτρο ακυκλικότητας σε γραφήματα καθώς και μία παράμετρος ένδειξης της ύπαρξης κυκλικών δομών σε αυτά. Στην παρούσα διπλωματική εργασία, συσχετίζουμε αυτές τις δύο παραμέτρους ορισμένες σε γραφήματα, δίνοντας μερικά άνω φράγματα της σκληρότητας ως συνάρτηση του δενδροπλάτους και αιτιολογούμε ότι δεν υπάρχει ανάλογο κάτω φράγμα.","The problems of computing the treewidth and the toughness of a graph are well-known NP-hard problems. Treewidth is a measure of connectivity in graphs as well as a measure of efficient computing for well-known NP-hard problems defined in graphs. Tougness on the other hand is a measure of acyclicity of a graph as well as an indicator parameter for the existence of cyclic structures in graphs. In this Master's thesis, we relate these two graph paramers, giving some upper bounds on toughness as a function of treewidth and justify that there does not exist a similar lower bound."],"dc:identifier":["uoadl:1321312","https://pergamos.lib.uoa.gr/uoa/dl/object/1321312"],"dc:language":["English"],"dc:title":["On the relation between treewidth and toughness"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:41Z"}