Γραμμικές απεικονίσεις γραφημάτων προχωρημένων δομών δεδομένων
Φόρτωση...
Ημερομηνία
Συγγραφείς
Παυλίδη, Μαρία-Ελένη
Pavlidi, Maria-Eleni
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Διάφορες γραμμικές απεικονίσεις γραφημάτων μπορούν να επιτευχθούν αξιοποιώντας γνωστές δομές
δεδομένων, με τις διατάξεις στοίβας και ουράς να είναι οι πλέον δημοφιλής. Στόχος μας είναι να
καθορίσουμε μια διάταξη των κορυφών και μια ανάθεση των ακμών σε σελίδες που επιτρέπουν στη δομή δεδομένων να επεξεργαστεί τις κορυφές-άκρες των ακμών κατά την καθορισμένη διάταξη.
Η παρούσα διατριβή εξετάζει τις rique απεικονίσεις γραφημάτων, οι οποίες προκύπτουν από την περιορισμένη-εισόδου διπλοουράς, γνωστή στην βιβλιογραφία επίσης ως rique. Η έρευνά μας επικεντρώνεται σε πλήρη γραφήματα και πλήρη διμερή γραφήματα, όπου παρουσιάζουμε φράγματα για τον ελάχιστο αριθμό σελίδων που απαιτούνται για οποιαδήποτε γραμμική απεικόνιση rique ενός δεδομένου γραφήματος. Στη μεταπτυχιακή αυτή διατριβή, βελτιώνουμε το υπάρχον άνω φράγμα για το πλήρες γράφημα Kn από ⌈ n/3 ⌉ σε ⌊ (n−1)/3 ⌋, και παρουσιάζουμε ένα νέο άνω φράγμα ⌊ (n−1/2 ⌋ − 1 για το πλήρες διμέρες γράφημα Kn,n. Τέλος, εισαγάγουμε μια) μοντελοποίηση βασισμένη σε SAT για τον υπολογισμό γραμμικών απεικονίσεων rique για δοθέντα γραφήματα. Επιβεβαιώνουμε την αποτελεσματικότητα της προσέγγισής μας υπολογίζοντας τον ελάχιστο αριθμό σελίδων που απαιτούνται σε γραμμικές απεικονίσεις rique γραφημάτων που είναι γνωστά στη βιβλιογραφία.
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.
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
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Όνομα επιβλέποντος
Μπέκος, Μιχαήλ
Εξεταστική επιτροπή
Παπαδόπουλος, Χάρης
Συμβώνης, Αντώνιος
Μπέκος, Μιχαήλ
Συμβώνης, Αντώνιος
Μπέκος, Μιχαήλ
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
LLGADS
Ονόματα συντελεστών
Αριθμός σελίδων
74 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution 3.0 United States