Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/39230Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Ντάσιου, Αικατερίνη Μαρία | el |
| dc.contributor.author | Ntasiou, Aikaterini Maria | en |
| dc.date.accessioned | 2025-07-25T06:23:36Z | - |
| dc.date.available | 2025-07-25T06:23:36Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/39230 | - |
| dc.rights | CC0 1.0 Universal | * |
| dc.rights.uri | http://creativecommons.org/publicdomain/zero/1.0/ | * |
| dc.subject | Hamiltonicity | en |
| dc.subject | Book Embeddings | en |
| dc.subject | Planar Graphs | en |
| dc.title | Μια SAT διατύπωση για την εξέταση της εικασίας του Barnette | el |
| dc.title | Engineering Barnette's conjecture with SAT | en |
| dc.type | masterThesis | - |
| heal.type | masterThesis | el |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.dateAvailable | 2025-07-25T06:24:36Z | - |
| heal.language | en | el |
| heal.access | free | el |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών | el |
| heal.publicationDate | 2025-07-15 | - |
| heal.abstract | ΄Ενα από τα πιο γνωστά προβλήματα στη Θεωρία Γραφημάτων αποτελεί η εικασία του Barnette, η οποία αν και διατυπώθηκε πριν αρκετές δεκαετίες, εξ- ακολουθεί να παραμένει ανοικτό πρόβλημα. Η εικασία υποστηρίζει ότι κάθε 3- κανονικό, 3-συνδεδεμένο, διμερές, επίπεδο γράφημα είναι Hamiltonian, δηλαδή, υπάρχει κύκλος που να διέρχεται από όλες τις κορυφές του γραφήματος ακριβώς μία φορά. Στην παρούσα μεταπτυχιακή διατριβή προτείνουμε μία SAT διατύπωση του προβλήματος του ελέγχου ύπαρξης Hamilton κύκλων σε επίπεδα γραφήματα και την αξιοποιούμε με σκοπό τη διερεύνηση της εικασίας του Barnette. Αξιολο- γούμε πειραματικά μία υλοποίηση αυτής της διατύπωσης σε τέσσερις κατηγορίες Barnette γραφημάτων που δημιουργήσαμε χρησιμοποιώντας διαφορετικές μεθό- δους. | el |
| heal.abstract | One of the most well-known problems in Graph Theory is Barnette’s conjecture, which although formulated several decades ago, is still open. The conjecture states that every 3-regular, 3-connected, bipartite, planar graph is Hamiltonian, that is, there is a cycle that passes through all the vertices of the graph exactly ones. In this thesis, we give a SAT-based formulation for testing the existence of Hamilton cycles in planar graphs and we use it to investigate Barnette’s conjecture. We experimentally evaluate an implementation of this formulation on four categories of Barnette graphs generated using different methods. | en |
| heal.advisorName | Μπέκος, Μιχαήλ | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Μπέκος, Μιχαήλ | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | el |
| heal.numberOfPages | 43 | el |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Master_Thesis_Ntasiou.pdf | 598.19 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
