Γραμμικές απεικονίσεις γραφημάτων προχωρημένων δομών δεδομένων
| 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.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.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | el |
| heal.access | free | el |
| heal.advisorName | Μπέκος, Μιχαήλ | el |
| heal.bibliographicCitation | LLGADS | en |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Συμβώνης, Αντώνιος | el |
| heal.committeeMemberName | Μπέκος, Μιχαήλ | el |
| heal.dateAvailable | 2023-07-11T10:35:31Z | |
| heal.fullTextAvailability | true | |
| heal.language | en | el |
| heal.numberOfPages | 74 σ. | el |
| heal.publicationDate | 2023-07 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών | el |
| heal.type | masterThesis | el |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. Παυλίδη Μαρία Ελένη (2023).pdf
- Μέγεθος:
- 3.95 MB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 3.22 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: