Perustieteiden korkeakoulun väitöskirjat ovat saatavilla yliopiston ylläpitämässä avoimessa Aaltodoc-julkaisuarkistossa.
Väitös, tietojenkäsittelytiede, DI Minoo Zarsav
Kuinka geometrinen rakenne mahdollistaa uusia tuloksia ja algoritmeja kaksiosaisissa graafiongelmissa.
Väitös Aalto-yliopiston perustieteiden korkeakoulusta, tietotekniikan laitokselta.
Väitös Aalto-yliopiston perustieteiden korkeakoulusta, tietotekniikan laitokselta.
Väitöskirjan nimi: Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry
³Õä¾±³Ù³Ù±ð±ô¾±Âáä: Minoo Zarsav
³Õ²¹²õ³Ù²¹±¹Ã¤¾±³Ù³ÙäÂáä: apulaisprofessori Erik Jan van Leeuwen, Utrecht University, Alankomaat
Kustos: professori Lauri Savioja, Aalto-yliopiston perustieteiden korkeakoulu
Väitöstilaisuus tietojenkäsittelytieteessä: Minoo Zarsav
DI Minoo Zarsav väittelee tohtoriksi 25. toukokuuta 2026 klo 12 luentosalissa M1 (M232), Kandidaattikeskus, Otakaari 1, Espoo.
Väitöskirjan nimi on
Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry.
Väitöskirja kuuluu teoreettisen tietojenkäsittelytieteen alaan, erityisesti kombinatoriikan, graafiteorian ja algoritmien tutkimukseen. Työssä esitetään uusia rakenteellisia ja ekstremaalisia tuloksia geometrisista esityksistä syntyville kaksiosaisille graafeille sekä kehitetään algoritmisia viitekehyksiä klassisiin vaikeisiin ongelmiin, kuten maksimaalisen tasapainoisen biklikin ongelmaan. Tulokset osoittavat, kuinka geometriset rajoitteet tuottavat rakenteellista harvuutta ja mahdollistavat paremmat approksimaatiotakuut.
Vastaväittäjänä toimii apulaisprofessori Erik Jan van Leeuwen (Utrechtin yliopisto) ja kustoksena professori Lauri Savioja (Aalto-yliopisto). Väitöskirja on julkisesti saatavilla Aalto-yliopiston julkaisupalvelussa.
Avainsanat: kaksiosaiset graafit, Ferrers-dimensio, geometriset leikkausgraafit, Zarankiewiczin ongelma, biklikit (bicliques), approksimaatioalgoritmit
Linkki väitöskirjan sähköiseen esittelykappaleeseen (esillä 7 päivää ennen väitöstä): .
Perustieteiden korkeakoulu väitöskirjat
Zoom pikaopas