{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:5402752"},"canonical_url":"https://search.dev.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:5402752","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Faster Even-Cycle Listing via Unbalanced Supersaturation","abstract":"Η παρούσα διπλωματική εργασία μελετά το θεμελιώδες πρόβλημα της απαρίθμησης κύκλων άρτιου μήκους υπό το πρίσμα της ακραίας θεωρίας γραφημάτων. Κεντρική ιδέα είναι ότι η δομική πληροφορία για τον αριθμό των κύκλων άρτιου μήκους σε διμερή γραφήματα μπορεί να μετατραπεί σε φράγματα για τον χρόνο εκτέλεσης αλγορίθμων απαρίθμησης κύκλων. Κύριο αποτέλεσμα της εργασίας είναι μια ασθενής μορφή της Εικασίας Μη Ισορροπημένου Υπερκορεσμού για άρτιους κύκλους. Αποδεικνύουμε ότι ένα διμερές γράφημα \\(G=(A\\cup B,E)\\) με επαρκώς πολλές ακμές ως προς το κατώφλι \\( \\max\\{|A|,|B|\\}\\cdot\\min\\{|A|,|B|\\}^{1/k} \\) πρέπει να περιέχει πολλές εμφανίσεις \\(C_{2k}\\). Παρότι το αποτέλεσμα αυτό αποτελεί ένα βήμα προς την πλήρη εικασία, παρέχει ήδη επαρκή πληροφορία για τις αλγοριθμικές εφαρμογές που εξετάζονται στην παρούσα εργασία. Χρησιμοποιώντας αυτό το ακραίο φράγμα, επανεξετάζουμε το πλαίσιο ανάλυσης των Williams και Westover για την απαρίθμηση άρτιων κύκλων. Αυτό οδηγεί σε μια βελτιωμένη ανάλυση του χρόνου εκτέλεσης, η οποία ισοφαρίζει την τρέχουσα βέλτιστη επίδοση για την απαρίθμηση \\(C_6\\), αποφεύγοντας όμως τη χρήση υπολογιστή~\\cite{williams2025listingSparse}. Επιπλέον, βελτιώνει το προηγουμένως γνωστό βέλτιστο φράγμα για την απαρίθμηση \\(C_{2k}\\) για κάθε \\(k\\ge 4\\), το οποίο οφείλεται στους Alon, Yuster και Zwick~\\cite{williams2025listingSparse,alon1997finding}. Επεκτείνουμε επίσης τη συζήτηση στα υπεργραφήματα. Το γράφημα πρόσπτωσης δίνει μια γενική αναγωγή από την απαρίθμηση κύκλων Berge σταθερού μήκους \\(\\ell\\) στην απαρίθμηση κύκλων μήκους \\(2\\ell\\) σε απλά γραφήματα. Επιπλέον, δίνουμε μια άμεση αναγωγή μέσω του επισημασμένου \\(2\\)-σκειώδες γραφήματος για την απαρίθμηση όλων των κύκλων Berge μήκους \\(\\ell\\) που περνούν από μια προκαθορισμένη κορυφή του υπεργραφήματος.","abstract_html":"Η παρούσα διπλωματική εργασία μελετά το θεμελιώδες πρόβλημα της απαρίθμησης κύκλων άρτιου μήκους υπό το πρίσμα της ακραίας θεωρίας γραφημάτων. Κεντρική ιδέα είναι ότι η δομική πληροφορία για τον αριθμό των κύκλων άρτιου μήκους σε διμερή γραφήματα μπορεί να μετατραπεί σε φράγματα για τον χρόνο εκτέλεσης αλγορίθμων απαρίθμησης κύκλων. Κύριο αποτέλεσμα της εργασίας είναι μια ασθενής μορφή της Εικασίας Μη Ισορροπημένου Υπερκορεσμού για άρτιους κύκλους. Αποδεικνύουμε ότι ένα διμερές γράφημα \\(G=(A\\cup B,E)\\) με επαρκώς πολλές ακμές ως προς το κατώφλι <span class=\"etd-inline-math\"> \\max\\{|A|,|B|\\}\\cdot\\min\\{|A|,|B|\\}<sup>1/k</sup> </span> πρέπει να περιέχει πολλές εμφανίσεις <span class=\"etd-inline-math\">C<sub>2k</sub></span>. Παρότι το αποτέλεσμα αυτό αποτελεί ένα βήμα προς την πλήρη εικασία, παρέχει ήδη επαρκή πληροφορία για τις αλγοριθμικές εφαρμογές που εξετάζονται στην παρούσα εργασία. Χρησιμοποιώντας αυτό το ακραίο φράγμα, επανεξετάζουμε το πλαίσιο ανάλυσης των Williams και Westover για την απαρίθμηση άρτιων κύκλων. Αυτό οδηγεί σε μια βελτιωμένη ανάλυση του χρόνου εκτέλεσης, η οποία ισοφαρίζει την τρέχουσα βέλτιστη επίδοση για την απαρίθμηση <span class=\"etd-inline-math\">C<sub>6</sub></span>, αποφεύγοντας όμως τη χρήση υπολογιστή~\\cite{williams2025listingSparse}. Επιπλέον, βελτιώνει το προηγουμένως γνωστό βέλτιστο φράγμα για την απαρίθμηση <span class=\"etd-inline-math\">C<sub>2k</sub></span> για κάθε \\(k\\ge 4\\), το οποίο οφείλεται στους Alon, Yuster και Zwick~\\cite{williams2025listingSparse,alon1997finding}. Επεκτείνουμε επίσης τη συζήτηση στα υπεργραφήματα. Το γράφημα πρόσπτωσης δίνει μια γενική αναγωγή από την απαρίθμηση κύκλων Berge σταθερού μήκους \\(\\ell\\) στην απαρίθμηση κύκλων μήκους \\(2\\ell\\) σε απλά γραφήματα. Επιπλέον, δίνουμε μια άμεση αναγωγή μέσω του επισημασμένου \\(2\\)-σκειώδες γραφήματος για την απαρίθμηση όλων των κύκλων Berge μήκους \\(\\ell\\) που περνούν από μια προκαθορισμένη κορυφή του υπεργραφήματος.","abstract_has_math":true,"creators":["ΠΑΝΑΓΗ ΑΝΤΡΕΑΣ","PANAGI ANTREAS"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-07-24T01:02:34Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5402752"],"render_values":[{"text":"uoadl:5402752","href":null,"code":true}]}]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5402752","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["ΠΑΝΑΓΗ ΑΝΤΡΕΑΣ","PANAGI ANTREAS"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5402752","https://pergamos.lib.uoa.gr/uoa/dl/object/5402752"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η παρούσα διπλωματική εργασία μελετά το θεμελιώδες πρόβλημα της απαρίθμησης κύκλων άρτιου μήκους υπό το πρίσμα της ακραίας θεωρίας γραφημάτων. Κεντρική ιδέα είναι ότι η δομική πληροφορία για τον αριθμό των κύκλων άρτιου μήκους σε διμερή γραφήματα μπορεί να μετατραπεί σε φράγματα για τον χρόνο εκτέλεσης αλγορίθμων απαρίθμησης κύκλων. Κύριο αποτέλεσμα της εργασίας είναι μια ασθενής μορφή της Εικασίας Μη Ισορροπημένου Υπερκορεσμού για άρτιους κύκλους. Αποδεικνύουμε ότι ένα διμερές γράφημα \\(G=(A\\cup B,E)\\) με επαρκώς πολλές ακμές ως προς το κατώφλι \\( \\max\\{|A|,|B|\\}\\cdot\\min\\{|A|,|B|\\}^{1/k} \\) πρέπει να περιέχει πολλές εμφανίσεις \\(C_{2k}\\). Παρότι το αποτέλεσμα αυτό αποτελεί ένα βήμα προς την πλήρη εικασία, παρέχει ήδη επαρκή πληροφορία για τις αλγοριθμικές εφαρμογές που εξετάζονται στην παρούσα εργασία. Χρησιμοποιώντας αυτό το ακραίο φράγμα, επανεξετάζουμε το πλαίσιο ανάλυσης των Williams και Westover για την απαρίθμηση άρτιων κύκλων. Αυτό οδηγεί σε μια βελτιωμένη ανάλυση του χρόνου εκτέλεσης, η οποία ισοφαρίζει την τρέχουσα βέλτιστη επίδοση για την απαρίθμηση \\(C_6\\), αποφεύγοντας όμως τη χρήση υπολογιστή~\\cite{williams2025listingSparse}. Επιπλέον, βελτιώνει το προηγουμένως γνωστό βέλτιστο φράγμα για την απαρίθμηση \\(C_{2k}\\) για κάθε \\(k\\ge 4\\), το οποίο οφείλεται στους Alon, Yuster και Zwick~\\cite{williams2025listingSparse,alon1997finding}. Επεκτείνουμε επίσης τη συζήτηση στα υπεργραφήματα. Το γράφημα πρόσπτωσης δίνει μια γενική αναγωγή από την απαρίθμηση κύκλων Berge σταθερού μήκους \\(\\ell\\) στην απαρίθμηση κύκλων μήκους \\(2\\ell\\) σε απλά γραφήματα. Επιπλέον, δίνουμε μια άμεση αναγωγή μέσω του επισημασμένου \\(2\\)-σκειώδες γραφήματος για την απαρίθμηση όλων των κύκλων Berge μήκους \\(\\ell\\) που περνούν από μια προκαθορισμένη κορυφή του υπεργραφήματος.","This thesis studies the fundamental problem of listing even-length cycles through the lens of extremal graph theory. A central theme is that structural information on the number of even-length cycles in bipartite graphs can be converted into running-time bounds for cycle-listing algorithms. The main result is a weak form of the Unbalanced Supersaturation Conjecture for even cycles. We prove that a bipartite graph \\(G=(A\\cup B,E)\\) with sufficiently many edges relative to the threshold \\( \\max\\{|A|,|B|\\}\\cdot\\min\\{|A|,|B|\\}^{1/k} \\) must contain many copies of \\(C_{2k}\\). Although this result constitutes a step toward the full conjecture, it already provides sufficient information for the algorithmic applications considered in this work. Using this extremal bound, we revisit the analysis framework of Williams and Westover for listing even cycles. This yields a refined running-time analysis that matches the state of the art for listing \\(C_6\\), while avoiding the computer-assisted analysis used in their work~\\cite{williams2025listingSparse}. Moreover, it improves the previously known state-of-the-art bound for listing \\(C_{2k}\\) for every \\(k\\ge 4\\), due to Alon, Yuster, and Zwick~\\cite{williams2025listingSparse,alon1997finding}. We also extend the discussion to hypergraphs. The incidence graph gives a global reduction from listing Berge cycles of fixed length \\(\\ell\\) to listing graph cycles of length \\(2\\ell\\). In addition, a direct labelled-\\(2\\)-shadow reduction lists all Berge cycles of length \\(\\ell\\) passing through a prescribed hypergraph vertex."]},{"key":"dc:title","label":"Title","values":["Faster Even-Cycle Listing via Unbalanced Supersaturation"]}]}],"canonical_facts":{"dc:creator":["ΠΑΝΑΓΗ ΑΝΤΡΕΑΣ","PANAGI ANTREAS"],"dc:date":["2026"],"dc:description":["Η παρούσα διπλωματική εργασία μελετά το θεμελιώδες πρόβλημα της απαρίθμησης κύκλων άρτιου μήκους υπό το πρίσμα της ακραίας θεωρίας γραφημάτων. Κεντρική ιδέα είναι ότι η δομική πληροφορία για τον αριθμό των κύκλων άρτιου μήκους σε διμερή γραφήματα μπορεί να μετατραπεί σε φράγματα για τον χρόνο εκτέλεσης αλγορίθμων απαρίθμησης κύκλων. Κύριο αποτέλεσμα της εργασίας είναι μια ασθενής μορφή της Εικασίας Μη Ισορροπημένου Υπερκορεσμού για άρτιους κύκλους. Αποδεικνύουμε ότι ένα διμερές γράφημα \\(G=(A\\cup B,E)\\) με επαρκώς πολλές ακμές ως προς το κατώφλι \\( \\max\\{|A|,|B|\\}\\cdot\\min\\{|A|,|B|\\}^{1/k} \\) πρέπει να περιέχει πολλές εμφανίσεις \\(C_{2k}\\). Παρότι το αποτέλεσμα αυτό αποτελεί ένα βήμα προς την πλήρη εικασία, παρέχει ήδη επαρκή πληροφορία για τις αλγοριθμικές εφαρμογές που εξετάζονται στην παρούσα εργασία. Χρησιμοποιώντας αυτό το ακραίο φράγμα, επανεξετάζουμε το πλαίσιο ανάλυσης των Williams και Westover για την απαρίθμηση άρτιων κύκλων. Αυτό οδηγεί σε μια βελτιωμένη ανάλυση του χρόνου εκτέλεσης, η οποία ισοφαρίζει την τρέχουσα βέλτιστη επίδοση για την απαρίθμηση \\(C_6\\), αποφεύγοντας όμως τη χρήση υπολογιστή~\\cite{williams2025listingSparse}. Επιπλέον, βελτιώνει το προηγουμένως γνωστό βέλτιστο φράγμα για την απαρίθμηση \\(C_{2k}\\) για κάθε \\(k\\ge 4\\), το οποίο οφείλεται στους Alon, Yuster και Zwick~\\cite{williams2025listingSparse,alon1997finding}. Επεκτείνουμε επίσης τη συζήτηση στα υπεργραφήματα. Το γράφημα πρόσπτωσης δίνει μια γενική αναγωγή από την απαρίθμηση κύκλων Berge σταθερού μήκους \\(\\ell\\) στην απαρίθμηση κύκλων μήκους \\(2\\ell\\) σε απλά γραφήματα. Επιπλέον, δίνουμε μια άμεση αναγωγή μέσω του επισημασμένου \\(2\\)-σκειώδες γραφήματος για την απαρίθμηση όλων των κύκλων Berge μήκους \\(\\ell\\) που περνούν από μια προκαθορισμένη κορυφή του υπεργραφήματος.","This thesis studies the fundamental problem of listing even-length cycles through the lens of extremal graph theory. A central theme is that structural information on the number of even-length cycles in bipartite graphs can be converted into running-time bounds for cycle-listing algorithms. The main result is a weak form of the Unbalanced Supersaturation Conjecture for even cycles. We prove that a bipartite graph \\(G=(A\\cup B,E)\\) with sufficiently many edges relative to the threshold \\( \\max\\{|A|,|B|\\}\\cdot\\min\\{|A|,|B|\\}^{1/k} \\) must contain many copies of \\(C_{2k}\\). Although this result constitutes a step toward the full conjecture, it already provides sufficient information for the algorithmic applications considered in this work. Using this extremal bound, we revisit the analysis framework of Williams and Westover for listing even cycles. This yields a refined running-time analysis that matches the state of the art for listing \\(C_6\\), while avoiding the computer-assisted analysis used in their work~\\cite{williams2025listingSparse}. Moreover, it improves the previously known state-of-the-art bound for listing \\(C_{2k}\\) for every \\(k\\ge 4\\), due to Alon, Yuster, and Zwick~\\cite{williams2025listingSparse,alon1997finding}. We also extend the discussion to hypergraphs. The incidence graph gives a global reduction from listing Berge cycles of fixed length \\(\\ell\\) to listing graph cycles of length \\(2\\ell\\). In addition, a direct labelled-\\(2\\)-shadow reduction lists all Berge cycles of length \\(\\ell\\) passing through a prescribed hypergraph vertex."],"dc:identifier":["uoadl:5402752","https://pergamos.lib.uoa.gr/uoa/dl/object/5402752"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Faster Even-Cycle Listing via Unbalanced Supersaturation"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-07-24T01:02:34Z"}