mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Maria Petropanagiotaki Anonymously browsing from 54.80.146.251 at 21:24:45, 20-11-2017. login

MSc thesis of Maria Petropanagiotaki

Παραμετρικοί Αλγόριθμοι και Μητροειδή η χρήση των συνόλων αντιπροσώπευσης

Supervisor: Dimitrios M. Thilikos

Έστω M = (E,I) μητροειδές και S = {S1,...,St} οικογένεια υποσυνόλων του E με |Si| = p ∀i ∈ {1, . . . , t}. Μια υποοικογένεια S′ ⊆ S ονομάζεται q-αντιπροσωπευτική της S, αν για κάθε σύνολο της οικογένειας S που μπορεί να επεκταθεί σε μεγαλύτερο ανεξάρτητο σύνολο προσθέτοντας του q νέα στοιχεία υπάρχει και κάποιο σύνολο της υποοικογένειας S′, το οποίο μπορεί να επεκταθεί σε μεγαλύτερο ανεξάρτητο σύνολο προσθέτοντας του τα ίδια q στοιχεία. Από το Θεώρημα Δύο Οικογενειών του Bollobás και τη γενικευσή του σε διανυσματικούς χώρους από τον Lovász, προκύπτει ότι υπάρχει q-αντιπροσωπευτική οικογένεια με το πολύ (p+q) ανά p σύνολα. Σε αυτήν την εργασία, δίνουμε δύο αλγορίθμους για την κατασκευή αντιπροσωπευτικής οικογένειας μεγέθους (p+q) ανά p. Ο πρώτος αλγόριθμος αφορά τα γραμμικά μητροειδή και «αλγοριθμοποιεί» την από- δειξη του Lovász κατασκευάζοντας οικογένεια σε χρόνο πολυωνυμικό ως προς (p+q) ανά p, t και τον χρόνο που απαιτείται για την πραγματοποίηση μιας πράξης σε κάποιο σώμα F. Ο δεύτερος αφορά μόνο τα ομοιόμορφα μητροειδή και τρέχει σε O((1 − x)^{−q} · 2^{o(p+q)} · t · log n) χρόνο. Στη συνέχεια, δείχνουμε πως υπολογίζοντας αποδοτικά αντιπροσωπευτικές οικογένειες, μπορούμε να κατασκευάσουμε γρήγορους παραμετρικούς αλγορίθμους για τα ακόλουθα προβλήματα: ΤΟΜΗ l-ΜΗΤΡΟΕΙΔΩΝ, ΜΑΚΡΥΣ ΚΑΤΕΥΘΥΝΟΜΕΝΟΣ ΚΥΚΛΟΣ και k-ΜΟΝΟΠΑΤΙ.

Defended: Nov. 4, 2016.

Scientific committee

Download

Download thesis.

Reporter

Page updates

No recent updates.

Feeds RSS and Atom feeds

posts
all posts RSS
news RSS
announcements RSS
website news RSS
events
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.