Sperner Capacity of Directed Graphs
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology |
Diplomityö
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Authors
Date
2005
Department
Major/Subject
Tietojenkäsittelyteoria
Mcode
T-79
Degree programme
Language
en
Pages
76
Series
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.Description
Supervisor
Orponen, PekkaThesis advisor
Östergård, PatricKeywords
Shannon capacity, nollavirhekapasiteetti, Sperner capacity, Shannon-kapasiteetti, tabu search, Sperner-kapasiteetti, transitive clique, tabuhaku, zero-error capacity, transitiivinen klikki