Sperner Capacity of Directed Graphs
| dc.contributor | Aalto-yliopisto | fi |
| dc.contributor | Aalto University | en |
| dc.contributor.advisor | Östergård, Patric | |
| dc.contributor.author | Kiviluoto, Lasse | |
| dc.contributor.department | Sähkö- ja tietoliikennetekniikan osasto | fi |
| dc.contributor.school | Teknillinen korkeakoulu | fi |
| dc.contributor.school | Helsinki University of Technology | en |
| dc.contributor.supervisor | Orponen, Pekka | |
| dc.date.accessioned | 2020-12-04T19:48:28Z | |
| dc.date.available | 2020-12-04T19:48:28Z | |
| dc.date.issued | 2005 | |
| dc.description.abstract | Vielä tänä päivänäkin on ratkaisematta C.E. Shannonin asettama kysymys kohisevan kanavan nollavirhekapasiteetista. Diskreetille muistittomalle kanavalle nollavirhekapasiteetti voidaan määrittää karakteristisen graafin Shannon-kapasiteettina. Shannon-kapasiteetin määrittäminen johtaa maksimiklikkiongelmaan potenssigraafeissa. Shannon-kapasiteetti voidaan yleistää suunnatuille graafeille ja tätä kapasiteettia kutsutaan Sperner-kapasiteetiksi. Sperner-kapasiteetin määrittäminen johtaa transitiivisten klikkien hakuun suunnatuissa graafeissa. Tutkimus Sperner-kapasiteetin osalta on keskittynyt lähinnä ylärajojen laskemismenetelmien kehittämiseen. Tuloksia Sperner-kapasiteetista löytyy lähinnä vain sykleille ja muunlaisista yli kolmen solmun graafeista tiedetään hyvin vähän. Tässä tutkielmassa tehdään lyhyt katselmus kehitettyihin Sperner-kapasiteetin rajojen laskemismenetelmiin. Transitiivisten klikkien hakuun esitetään kaksi eksaktia algoritmia sekä stokastinen tabuhakumenetelmä. Käyttäen näitä algoritmeja sekä ylärajojen laskemismenetelmiä yritetään ratkaista Sperner-kapasiteetti mielivaltaisille alle viisi solmua sisältäville suunnatuille graafeille. Lopuksi tarkastellaan suunnistettuja komplementtisyklejä, jotka eivät sisällä transitiivia kolmioita ja annetaan näiden graafien Sperner-kapasiteeteille uusia alarajoja. | fi |
| dc.format.extent | 76 | |
| dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/93114 | |
| dc.identifier.urn | URN:NBN:fi:aalto-2020120451949 | |
| dc.language.iso | en | en |
| dc.programme.major | Tietojenkäsittelyteoria | fi |
| dc.programme.mcode | T-79 | fi |
| dc.rights.accesslevel | closedAccess | |
| dc.subject.keyword | Shannon capacity | en |
| dc.subject.keyword | nollavirhekapasiteetti | fi |
| dc.subject.keyword | Sperner capacity | en |
| dc.subject.keyword | Shannon-kapasiteetti | fi |
| dc.subject.keyword | tabu search | en |
| dc.subject.keyword | Sperner-kapasiteetti | fi |
| dc.subject.keyword | transitive clique | en |
| dc.subject.keyword | tabuhaku | fi |
| dc.subject.keyword | zero-error capacity | en |
| dc.subject.keyword | transitiivinen klikki | fi |
| dc.title | Sperner Capacity of Directed Graphs | en |
| dc.title | Suunnattujen graafien Sperner-kapasiteetti | fi |
| dc.type.okm | G2 Pro gradu, diplomityö | |
| dc.type.ontasot | Master's thesis | en |
| dc.type.ontasot | Pro gradu -tutkielma | fi |
| dc.type.publication | masterThesis | |
| local.aalto.digiauth | ask | |
| local.aalto.digifolder | Aalto_35146 | |
| local.aalto.idinssi | 30399 | |
| local.aalto.openaccess | no |