Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/32966Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Παυλίδη, Μαρία-Ελένη | el |
| dc.contributor.author | Pavlidi, Maria-Eleni | en |
| dc.date.accessioned | 2023-07-11T10:34:30Z | - |
| dc.date.available | 2023-07-11T10:34:30Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/32966 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.12765 | - |
| dc.rights | Attribution 3.0 United States | * |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | http://creativecommons.org/licenses/by/3.0/us/ | * |
| dc.subject | Απεικονίσεις | el |
| dc.title | Γραμμικές απεικονίσεις γραφημάτων προχωρημένων δομών δεδομένων | el |
| dc.title | Linear graphs layouts of advanced data structures | en |
| dc.type | masterThesis | - |
| dc.type | info:eu-repo/semantics/masterThesis | * |
| heal.type | masterThesis | el |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.dateAvailable | 2023-07-11T10:35:31Z | - |
| heal.language | en | el |
| heal.access | free | el |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών | el |
| heal.publicationDate | 2023-07 | - |
| heal.bibliographicCitation | LLGADS | en |
| heal.abstract | Διάφορες γραμμικές απεικονίσεις γραφημάτων μπορούν να επιτευχθούν αξιοποιώντας γνωστές δομές δεδομένων, με τις διατάξεις στοίβας και ουράς να είναι οι πλέον δημοφιλής. Στόχος μας είναι να καθορίσουμε μια διάταξη των κορυφών και μια ανάθεση των ακμών σε σελίδες που επιτρέπουν στη δομή δεδομένων να επεξεργαστεί τις κορυφές-άκρες των ακμών κατά την καθορισμένη διάταξη. Η παρούσα διατριβή εξετάζει τις rique απεικονίσεις γραφημάτων, οι οποίες προκύπτουν από την περιορισμένη-εισόδου διπλοουράς, γνωστή στην βιβλιογραφία επίσης ως rique. Η έρευνά μας επικεντρώνεται σε πλήρη γραφήματα και πλήρη διμερή γραφήματα, όπου παρουσιάζουμε φράγματα για τον ελάχιστο αριθμό σελίδων που απαιτούνται για οποιαδήποτε γραμμική απεικόνιση rique ενός δεδομένου γραφήματος. Στη μεταπτυχιακή αυτή διατριβή, βελτιώνουμε το υπάρχον άνω φράγμα για το πλήρες γράφημα Kn από ⌈ n/3 ⌉ σε ⌊ (n−1)/3 ⌋, και παρουσιάζουμε ένα νέο άνω φράγμα ⌊ (n−1/2 ⌋ − 1 για το πλήρες διμέρες γράφημα Kn,n. Τέλος, εισαγάγουμε μια) μοντελοποίηση βασισμένη σε SAT για τον υπολογισμό γραμμικών απεικονίσεων rique για δοθέντα γραφήματα. Επιβεβαιώνουμε την αποτελεσματικότητα της προσέγγισής μας υπολογίζοντας τον ελάχιστο αριθμό σελίδων που απαιτούνται σε γραμμικές απεικονίσεις rique γραφημάτων που είναι γνωστά στη βιβλιογραφία. | el |
| heal.abstract | Various linear graph layouts can be achieved by leveraging familiar data structures, with stack and queue layouts being the most prominent examples. The objective in this context is to determine a vertex order and an edge-partitioning into pages that allow the data structure to process the endpoints of the edges in the specified order. This thesis examines rique layouts of graphs, which are obtained by utilizing the restricted-input double-ended queue, also known as rique. Our research focuses on complete graphs and complete bipartite graphs, where we present bounds on their rique numbers, where the rique number represents the minimum number of pages needed for any rique layout of a given graph. We improve the existing upper bound for the complete graph Kn from ⌈ n/3 ⌉ to ⌊ (n−1)/3 ⌋, and we introduce a new upper bound of ⌊ (n−1)/2 ⌋ − 1 for the complete bipartite graph Kn,n. Finally, we propose a SAT-based formulation to compute the rique number of various graphs. We confirm the effectiveness of our approach by implementing it and by calculating the rique number of various graphs that are named in the literature. | en |
| heal.advisorName | Μπέκος, Μιχαήλ | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Συμβώνης, Αντώνιος | el |
| heal.committeeMemberName | Μπέκος, Μιχαήλ | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | el |
| heal.numberOfPages | 74 σ. | el |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. Παυλίδη Μαρία Ελένη (2023).pdf | 4.04 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
