Back to search

National and Kapodistrian University of Athens

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

Abstract

dc:description

Έστω 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-ΜΟΝΟΠΑΤΙ.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Πετροπαναγιωτάκη Μαρία
  • Petropanagiotaki Maria

Subjects

dc:subject × 2

Rights

Language dc:language
Ελληνικά, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:1325895

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Πετροπαναγιωτάκη Μαρία; Petropanagiotaki Maria. Παραμετρικοί Αλγόριθμοι και Μητροειδή: η χρήση των συνόλων αντιπροσώπευσης. 2016. https://pergamos.lib.uoa.gr/uoa/dl/object/1325895