search query: @keyword nollavirhekapasiteetti / total: 1
reference: 1 / 1
« previous | next »
Author: | Kiviluoto, Lasse |
Title: | Sperner Capacity of Directed Graphs |
Suunnattujen graafien Sperner-kapasiteetti | |
Publication type: | Master's thesis |
Publication year: | 2005 |
Pages: | 76 Language: eng |
Department/School: | Sähkö- ja tietoliikennetekniikan osasto |
Main subject: | Tietojenkäsittelyteoria (T-79) |
Supervisor: | Orponen, Pekka |
Instructor: | Östergård, Patric |
OEVS: | Electronic archive copy is available via Aalto Thesis Database.
Instructions Reading digital theses in the closed network of the Aalto University Harald Herlin Learning CentreIn the closed network of Learning Centre you can read digital and digitized theses not available in the open network. The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/ You can read theses on the Learning Centre customer computers, which are available on all floors.
Logging on to the customer computers
Opening a thesis
Reading the thesis
Printing the thesis
|
Location: | P1 Ark S80 | Archive |
Keywords: | Shannon capacity Sperner capacity tabu search transitive clique zero-error capacity nollavirhekapasiteetti Shannon-kapasiteetti Sperner-kapasiteetti tabuhaku transitiivinen klikki |
Abstract (fin): | 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. |
ED: | 2005-12-16 |
INSSI record number: 30399
+ add basket
« previous | next »
INSSI