Csaplár Viktor: Matroidmetszet orákulumkomplexitása

Egyéni Kutatómunka 2

2024/25 II. félév

Témavezető:
Bérczi Kristóf (ELTE TTK, Operációkutatási Tsz.)
Cím:
Matroidmetszet orákulumkomplexitása
Beszámoló:
---
Előadás:
---

Adott két matroid egy alaphalmazon, a független halmazok ismerete nélkül. Továbbá van két orákulum a két matroidra, melyeket meg tudunk hívni, és megmondják egy-egy általunk kiválasztott halmazról, hogy az független-e egy matroidban. Szeretnénk, az orákulumok minél kevesebb használatával adni egy algoritmust, amivel meg tudjuk adni a két matroid egy maximális közös független halmazát.