Faster Even-Cycle Listing via Unbalanced Supersaturation

Η παρούσα διπλωματική εργασία μελετά το θεμελιώδες πρόβλημα της απαρίθμησης κύκλων άρτιου μήκους υπό το πρίσμα της ακραίας θεωρίας γραφημάτων. Κεντρική ιδέα είναι ότι η δομική πληροφορία για τον αριθμό των κύκλων άρτιου μήκους σε διμερή γραφήματα μπορεί να μετατραπεί σε φράγματα για τον χρόνο εκτέλεσης αλγορίθμων απαρίθμησης κύκλων. Κύριο αποτέλεσμα της εργασίας είναι μια ασθενής μορφή της Εικασίας Μη Ισορροπημένου Υπερκορεσμού για άρτιους κύκλους. Αποδεικνύουμε ότι ένα διμερές γράφημα \(G=(A\cup B,E)\) με επαρκώς πολλές ακμές ως προς το κατώφλι \max\{|A|,|B|\}\cdot\min\{|A|,|B|\}^1/k πρέπει να περιέχει πολλές εμφανίσεις C_2k. Παρότι το αποτέλεσμα αυτό αποτελεί ένα βήμα προς την πλήρη εικασία, παρέχει ήδη επαρκή πληροφορία για τις αλγοριθμικές εφαρμογές που εξετάζονται στην παρούσα εργασία. Χρησιμοποιώντας αυτό το ακραίο φράγμα, επανεξετάζουμε το πλαίσιο ανάλυσης των Williams και Westover για την απαρίθμηση άρτιων κύκλων. Αυτό οδηγεί σε μια βελτιωμένη ανάλυση του χρόνου εκτέλεσης, η οποία ισοφαρίζει την τρέχουσα βέλτιστη επίδοση για την απαρίθμηση C₆, αποφεύγοντας όμως τη χρήση υπολογιστή~\cite{williams2025listingSparse}. Επιπλέον, βελτιώνει το προηγουμένως γνωστό βέλτιστο φράγμα για την απαρίθμηση C_2k για κάθε \(k\ge 4\), το οποίο οφείλεται στους Alon, Yuster και Zwick~\cite{williams2025listingSparse,alon1997finding}. Επεκτείνουμε επίσης τη συζήτηση στα υπεργραφήματα. Το γράφημα πρόσπτωσης δίνει μια γενική αναγωγή από την απαρίθμηση κύκλων Berge σταθερού μήκους \(\ell\) στην απαρίθμηση κύκλων μήκους \(2\ell\) σε απλά γραφήματα. Επιπλέον, δίνουμε μια άμεση αναγωγή μέσω του επισημασμένου \(2\)-σκειώδες γραφήματος για την απαρίθμηση όλων των κύκλων Berge μήκους \(\ell\) που περνούν από μια προκαθορισμένη κορυφή του υπεργραφήματος.

Authors dc:creator

• ΠΑΝΑΓΗ ΑΝΤΡΕΑΣ
• PANAGI ANTREAS

• Θετικές Επιστήμες
• Science

Language dc:language

English

Identifier

uoadl:5402752

OAI identifier oai:identifier

oai:lib.uoa.gr:uoadl:5402752