Το πρόβλημα του πλάτους αποκοπής σε σχεδόν κατωφλικά γραφήματα
| dc.contributor.author | Γκριμπαβιώτης, Ανδρέας | el |
| dc.date.accessioned | 2020-11-19T10:07:20Z | |
| dc.date.available | 2020-11-19T10:07:20Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/30310 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.10198 | |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Γραφήματα | el |
| dc.subject | Graphs | en |
| dc.title | Το πρόβλημα του πλάτους αποκοπής σε σχεδόν κατωφλικά γραφήματα | el |
| heal.abstract | Στη παρούσα εργασία μελετάμε το NP-δύσκολο πρόβλημα της εύρεσης του ελάχιστου πλάτους αποκοπής σε σχεδόν κατωφλικα γραφήματα. Στο πρόβλημα αυτό σκοπός μας είναι να βρούμε μια διάταξη των κορυφών ενός γραφήματος που ελαχιστοποιεί το μέγιστο πλήθος ακμών που περνάνε από κάθε τομή των κορυφών. Ως κλασικό πρόβλημα διάταξης κορυφών βρίσκει ποικίλες εφαρμογές. Πρώτα είχε εισαχθεί ως μοντελοποίηση για την ελαχιστοποίηση του πλήθους καναλιών ενός κυκλώματος σχεδίασης, ενώ αργότερα βρήκε εφαρμογές σε άλλες περιοχές όπως την αξιοπιστία δικτύου, αυτόματη σχεδίαση γραφημάτων, ανάκτηση πληροφορίας, ακόμα και ως υπορουτίνα για τον αλγόριθμο αποκοπής μιας επίπεδης επιφάνειας στο κλασικό πρόβλημα του περιοδεύοντος πωλητή. Καθώς το πρόβλημα παραμένει ΝP-δύσκολο ακόμα και σε κλάσεις γραφημάτων όπως τα διμερή (bipartite), διαχωρίσιμα (split), επίπεδα (planar) γραφήματα μελετάμε το πρόβλημα σε κλάσεις γραφημάτων που είναι ανοιχτή η υπολογιστική πολυπλοκότητα του προβλήματος. Από την θετική σκοπιά, είναι γνωστοί ορισμένοι αλγόριθμοι γραμμικού χρόνου για την κλάση των κατωφλικών (threshold) γραφημάτων και για την κλάση των διμερή μεταθετικών (bipartite permutation) γραφημάτων. Ως άμεση συνέπεια εξετάζουμε το πρόβλημα στην άμεση υπερκλάση των κατωφλικών γραφημάτων, γνωστή ως σχεδόν κατωφλικά γραφήματα. Βασιζόμενοι σε δομικές ιδιότητες των σχεδόν κατωφλικών γραφημάτων, αποδεικνύουμε χαρακτηρισμούς της βέλτιστης διάταξης που μας επιτρέπουν την σχεδίαση αλγορίθμου που τρέχει σε χρόνο Ο(2N) με που είναι γρηγορότερο από τον εκθετικό Ο(2n) αλγόριθμο για γενικά γραφήματα με n κορυφές. Επίσης δίνουμε έναν πολυωνυμικό αλγόριθμο για την υποκλάση των σχεδόν κατωφλικών γραφημάτων, που την ονομάζουμε 1-επιπέδου σχεδόν κατωφλικά γραφήματα. Προς την κατεύθυνση ανάπτυξης πολυωνυμικού αλγορίθμου για την γενική περίπτωση, παρουσιάζουμε αντιπαραδείγματα για πολλές ιδιότητες που θα περιμέναμε να έχει μια βέλτιστη διάταξη. Για τον σκοπό αυτό υλοποιήσαμε αρκετές τεχνικές που βοηθάνε την αντιμετώπιση του προβλήματος. Ωστόσο, αξίζει να σημειώσουμε ότι το υπολογιστικό πρόβλημα της εύρεσης ελάχιστου πλάτους αποκοπής σε σχεδόν κατωφλικά γραφήματα παραμένει ανοικτό. | el |
| heal.abstract | In this thesis we study the Cutwidth Minimization Problem in quasithreshold graphs, an NP-hard problem that consists of finding a linear layout of a graph so that the maximum linear cut of edges (i.e., the number of edges that cut a line between consecutive vertices) is minimized. As a well-studied layout problem finds many applications. The Cutwidth problem was first used as a model for the number of channels in an optimal layout of a circuit, to give a measure of the area needed to represent the graph in a VLSI layout when nodes are laid out in a row and more recently we find applications of this problem in network reliability, automatic graph drawing, information retrieval and as a subroutine for the cutting plane algorithm to solve the TSP. The problem remains NP-Hard even in graph classes such as the bipartite, the split and the planar graphs. Thus we study this problem in classes that it still remains open. In a positive side of view polynomial time algorithms exists for the subclass of thresholds and for the bipartite permutation graphs. As a consequence we study this problem in the direct superclass of quasi-threshold graphs. Based on the structural properties of the quasi-threshold graphs we prove several acclaims for the form of an optimal linear ordering, thus enabling us to design an algorithm that runs in time, where , that is faster than the algorithm for general graphs that runs in time. We also design a polynomial time algorithm for a subclass of the quasi-threshold graphs, that we call 1-level quasithreshold graphs. As we struggle to prove a polynomial time algorithm for the cutwidth problem in quasi-threshold graph we introduce counter examples for many properties one would expect to encounter in an optimal ordering. For this end we developed many techniques to tackle with the problem. We have to note, although, that the cutwidth problem for the quasi-threshold graphs remains open. | en |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 79-85 | el |
| heal.classification | Γραφήματα (Μαθηματικά) | |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Γλυνός, Νικόλαος | el |
| heal.committeeMemberName | Μπαλτζής, Σωκράτης | el |
| heal.dateAvailable | 2020-11-19T10:08:20Z | |
| heal.fullTextAvailability | true | |
| heal.language | el | |
| heal.numberOfPages | 101 σ. | |
| heal.publicationDate | 2015 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΓΚΡΙΜΠΑΒΙΩΤΗΣ ΑΝΔΡΕΑΣ 2015.pdf
- Μέγεθος:
- 1.59 MB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: