Practical performance of incremental topological sorting and cycle detection algorithms

Visa enkel post
dc.contributor.authorSigurðsson, Ragnar Lárus
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.date.accessioned2019-07-03T14:27:00Z
dc.date.available2019-07-03T14:27:00Z
dc.date.issued2017
dc.description.abstractAlgorithms become more advanced and asymptotic time bounds get lower but there is very little data on the actual performance of new algorithms. The aim of this thesis is to do empirical testing of the most recent incremental topological sorting and cycle detection algorithms in order to compare them and to provide an accessible guide to where each algorithm performs best. The algorithms are implemented as the articles describe them and compared on even grounds by measuring their performance by adding edges to graphs. For sparse graphs the HKMST-Sparse [7] algorithm performed best and HKMSTDense [7] for very dense graphs. The Pearce & Kelly [8] algorithm is a strong contender as it is extremely simple and has acceptable performance across all graph densities and performs best in the range 35-80% density.
dc.identifier.urihttps://hdl.handle.net/20.500.12380/248308
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectInformations- och kommunikationsteknik
dc.subjectData- och informationsvetenskap
dc.subjectInformation & Communication Technology
dc.subjectComputer and Information Science
dc.titlePractical performance of incremental topological sorting and cycle detection algorithms
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
local.programmeComputer science – algorithms, languages and logic (MPALG), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
248308.pdf
Storlek:
1.83 MB
Format:
Adobe Portable Document Format
Beskrivning:
Fulltext
Ladda ner
Samling
Examensarbeten för masterexamen