2026-09-24T07:06:01Zhttps://skemman.is/oai/request

oai:skemman.is:1946/296182019-08-30T07:49:14Zcom_1946_6870com_1946_6001col_1946_34325

Háskólinn í Reykjavík Alex William Cregten 1995- Hannes Hannesson 1995- Henning Arnór Úlfarsson 1981- 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 lagnetapró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/. 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/. 2018-02-15T16:29:16Z 2018-02-15T16:29:16Z 2018-02-15T16:29:17Z 2017-12-18T14:26:20Z 2017-12 http://hdl.handle.net/1946/29618 en https://github.com/rostam/GTea/ Tölvunarfræði Reiknirit Computer science Algorithms Implementation of a planarity testing method using PQ-Trees Thesis Bachelor's