Steinerjeva drevesa (Seminar DM)

Iz MaFiRaWiki

Steinerjeva drevesa

Mitja Bezenšek, FRI

Torek, 30. 3. 2010 od 10h do 11h, Plemljev seminar, Jadranska 19

Problem Steinerjevih dreves je definiran na sledeč način: podana je množica n točk T (imenovanih terminali) v prostoru Rd. Poišči množico dodatnih točk S (imenovanih Steinerjeve točke), tako, da bo dolžina minimalnega vpetega drevesa T \bigcup S minimalna. Pri tem za dolžino ponavadi vzamemo katero izmed običajnih metrik, npr. Evklidsko razdaljo.

Ogledali si bomo tehnike, ki se uporabljajo pri reševanju tega problema. Osredotočili se bomo na paralelne in porazdeljene algoritme.

Vabljeni!

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja