is Íslenska en English

Lokaverkefni (Bakkalár) Háskólinn í Reykjavík > Tölvunarfræðideild > BSc verkefni >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/29647

Titill: 
  • Implementation of a planarity testing method using PQ-Trees
Námsstig: 
  • Bakkalár
Útdráttur: 
  • Útdráttur er á ensku

    The website GTea is introduced where two planarity testing algorithms have been implemented. Of these two algorithms, one is a brute-force method and the other a much faster PQ-Tree method introduced by K. S. Booth and G. S. Lueker. The two algorithms are discussed and running times compared in detail. A prerequisite algorithm to the PQ-Tree method is examined and implemented, which determines an st-numbering. The algorithm was introduced by S. Even and R. E. Tarjan. Front-end additions to GTea are shown which involve the manual modification and creation of graphs. A discussion on where this project has left GTea and the next steps forward are examined. The codebase of GTea can be found at the following link: https://github.com/rostam/GTea/.

  • Vefsíðan GTea er kynnt, þar hafa verið útfærð tvö lagneta-prófana reiknirit. Af þessum reikniritum, þá nýtir annað sér jarðýtu aðferð, á meðan hitt er skilvirkara reiknirit sem nýtir sér gagnaskipanið PQ-Tré sem var kynnt af K. S. Booth og G. S. Lueker. Þessi reiknirit eru rædd og keyrslutímar þeirra eru bornir saman. Forsenda til að keyra PQ-Trája lagneta-prófana reikniritið, er að netið hafi st-tölusetningu, við ræðum útfærslu á reikniriti sem ákvarðar st-tölusetningu fyrir net, sem var kynnt af S. Even og R. E. Tarjan. Framenda lagfæringar á GTea sem leyfa handvirka breytingu og sköpun neta, og hugmyndir að viðbætum við GTea eru einnig ræddar. Kóðasafnið fyrir GTea er hægt að finna á eftirfarandi slóð: https://github.com/rostam/GTea/.

Tengd vefslóð: 
  • https://github.com/rostam/GTea/
Samþykkt: 
  • 20.2.2018
URI: 
  • http://hdl.handle.net/1946/29647


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
Planarity_testing_with_PQTrees.pdf480.4 kBOpinnHeildartextiPDFSkoða/Opna