Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Väitöskirjat
  • Näytä viite
  •   Etusivu
  • Trepo
  • Väitöskirjat
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

Approximation Algorithms for Some Topological Invariants of Graphs

Poranen, Timo (2004)

 
Avaa tiedosto
951-44-6128-2.pdf (906.7Kt)
Lataukset: 



Poranen, Timo
Tampere University Press Tampereen yliopisto
2004

Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Väitöspäivä
2004-10-22
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/urn:isbn:951-44-6128-2
Tiivistelmä
Topologinen graafiteoria tutkii graafien kuvauksia erilaisille pinnoille sekä näiden kuvausten ominaisuuksia. Porasen tietojenkäsittelytieteellisessä työssä on tarkasteltu isomorfisissa graafeissa muuttumattomina pysyvien topologisten ominaisuuksien tunnistamista. Tutkituilla algoritmeilla on sovelluksia graafien visualisoinnissa, piirilevyjen suunnittelussa sekä erilaisissa sijoitteluongelmissa.

Työssä esitetään useita uusia likimääräismenetelmiä seuraavien graafien topologisten ominaisuuksien laskemiseksi: suurimman tasoaligraafin koko, suurimman ulkotasoaligraafin koko, graafin paksuus ja ulkopaksuus. Näistä ongelmista kolme ensimmäistä kuuluu laskennallisesti vaikeiden eli NP-täydellisten ongelmien luokkaan. Ulkopaksuuden määräämisen laskennallista vaativuutta ei tunneta.

Uusia menetelmiä verrataan kirjallisuudessa aiemmin esitettyihin menetelmiin ja osoitetaan että kehitetyt algoritmit toimivat aiempia menetelmiä tehokkaammin sekä suoritusajan että ratkaisujen hyvyyden suhteen.

Lisäksi työssä esitetään myös uusia teoreettisia tuloksia graafin ulkopaksuden ylä- ja alarajan sekä kolmijakoisten graafien paksuuden ylärajan arviointiin. Työssä ratkaistaan osittain myös yli kolmekymmentä vuotta avoimena ollut kaksijakoisten graafien paksuuteen liittyvä ongelma.
 
Kokoelmat
  • Väitöskirjat [4549]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste