Algorithms for computing avoidable vertices and avoidable paths
| dc.contributor.author | Zisis, Athanasios | en |
| dc.contributor.author | Ζήσης, Αθανάσιος | el |
| dc.date.accessioned | 2022-05-13T10:38:56Z | |
| dc.date.available | 2022-05-13T10:38:56Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/31738 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.11553 | |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Avoidable vertices | en |
| dc.subject | Avoidable paths | en |
| dc.subject | Graph contraction | en |
| dc.subject | Nice minimal triangulation | en |
| dc.subject | S-excluded path | en |
| dc.subject | Protecting | en |
| dc.subject | Κόμβοι αποφυγής | el |
| dc.subject | Μονοπάτια αποφυγής | el |
| dc.title | Algorithms for computing avoidable vertices and avoidable paths | en |
| dc.title | Αλγόριθμοι για τον υπολογισμό κόμβων αποφυγής και μονοπατιών αποφυγής | el |
| heal.abstract | A simplicial vertex of a graph is a vertex whose neighborhood is a clique. It is known that listing all simplicial vertices can be done in O(nm) time or O(n ω ) time, where O(n ω ) is the time needed to perform a fast matrix multiplication. The notion of avoidable vertices generalizes the concept of simplicial vertices in the following way: a vertex u is avoidable if every induced path on three vertices with middle vertex u is contained in an induced cycle. We present algorithms for listing all avoidable vertices of a graph through the notion of minimal triangulations and common neighborhood detection. In particular we give algorithms with running times O(n 2m) and O(n 1+ω ), respectively. Additionally, we propose a faster algorithm that runs in time O(n 2 + m2 ), and thus matches the corresponding running time of listing the simplicial vertices on sparse graphs with m = O(n). Moreover, our results imply an optimal algorithm on cographs and O(nm)- time algorithm on chordal graphs. To complement our results, we consider their natural generalizations of avoidable edges and avoidable paths. We propose an O(nm)-time algorithm that recognizes whether a given induced path is avoidable. Finally, we compare the empirical performance of our proposed algorithms that are performed on the overall input graph as well as on its contracted sub graphs. To that end, we conduct a thorough experimental study to highlight the merits and weaknesses of each technique. | en |
| heal.abstract | Η κορυφή ενός γραφήματος της οποίας η γειτονιά είναι κλίκα, καλείται simpli cial. Είναι γνωστό ότι η εύρεση όλων των simplicial κορυφών ενός γραφήματος με n κορυφές και m ακμές μπορεί να επιτευχθεί σε O(nm) χρόνο ή O(n ω ) χρόνο, όπου O(n ω ) είναι ο χρόνος που απαιτείται για τον πολλαπλασιασμό πινάκων δι άστασης n × n. Η έννοια των κορυφών αποφυγής (avoidable vertices) αποτελεί γενίκευση της έννοιας των simplicial κορυφών με τον ακόλουθο τρόπο: μια κο ρυφή u είναι κορυφή αποφυγής (avoidable) εαν κάθε επαγόμενο μονοπάτι τριών κορυφών με μεσαία κορυφή την u περιέχεται σε έναν επαγόμενο κύκλο. Παρουσιάζουμε και αναλύουμε αλγόριθμους που σχεδιάσαμε για την εύρεση όλων των κορυφών αποφυγής ενός γραφήματος μέσω των εννοιών των minimal triangulations και της ανίχνευσης κοινής γειτονιάς. Πιο συγκεκριμένα, δίνουμε αλγόριθμους με πολυπλοκότητα χρόνου O(n 2m) και O(n 1+ω ), αντίστοιχα. Επι πλέον, προτείνουμε και έναν πιο γρήγορο αλγόριθμο με χρονική πολυπλοκότητα O(n 2 + m2 ), η οποία συμπίπτει με την αντίστοιχη πολυπλοκότητα χρόνου της εύρεσης των simplicial κορυφών σε αραιά γραφήματα όπου χαρακτηρίζονται από m = O(n). Αξίζει να σημειώσουμε ότι κατά την ανάλυση των συγκεκριμένων αλγορίθμων σχεδιάσαμε επιπλέον έναν βέλτιστο γραμμικό αλγόριθμο για τα cograph και έναν αλγόριθμο για τα chordal γραφήματα με πολυπλοκότητα χρόνου O(nm). Επεκτείνουμε τα αποτελέσματά μας, εξετάζοντας τις ακμές αποφυγής (avoid able edges) και, πιο γενικά, τα μονοπάτια αποφυγής (avoidable paths) καθώς αποτελούν την φυσική γενίκευση των κορυφών αποφυγής. Παρουσιάζουμε έναν αλγόριθμο χρονικής πολυπλοκότητας O(nm), ο οποίος αναγνωρίζει πότε ένα δω θέν επαγόμενο μονοπάτι (ή ακμή) είναι μονοπάτι (ή ακμή) αποφυγής. Τέλος, συγκρίνουμε την εμπειρική απόδοση των προτεινόμενων αλγορίθμων μας, που εκτελούνται στο συνολικό γράφημα εισόδου, καθώς και στα συρικνωμένα υπογραφήματά του. Για το σκοπό αυτό, διεξάγουμε μια διεξοδική πειραματική μελέτη για να αναδείξουμε τα πλεονεκτήματα και τις αδυναμίες κάθε προτεινόμενης τεχνικής. | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Παπαδόπουλος, Χάρης | el |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 58-72 | el |
| heal.classification | Algorithms | |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.dateAvailable | 2022-05-13T10:39:57Z | |
| heal.fullTextAvailability | true | |
| heal.language | en | |
| heal.numberOfPages | 72 σ. | |
| heal.publicationDate | 2021 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΖΗΣΗΣ ΑΘΑΝΑΣΙΟΣ 2021.pdf
- Μέγεθος:
- 857.73 KB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: