Practical performance of incremental topological sorting and cycle detection algorithms

Examensarbete för masterexamen

Please use this identifier to cite or link to this item:
Download file(s):
File Description SizeFormat 
248308.pdfFulltext1.88 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Practical performance of incremental topological sorting and cycle detection algorithms
Authors: Sigurðsson, Ragnar Lárus
Abstract: Algorithms 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.
Keywords: Informations- och kommunikationsteknik;Data- och informationsvetenskap;Information & Communication Technology;Computer and Information Science
Issue Date: 2017
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
Collection:Examensarbeten för masterexamen // Master Theses

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.