Benchmarking optimised algorithms for transitive closure

V. Pieterse, L.G.W.A. Cleophas

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    We investigate the impact of using different algorithmic techniques and data representations in algorithms to calculate the transitive closure of a finite binary relation. These techniques are change monitor, loop fusion, loop tiling and short-circuiting. We explain them and how they are applied in the algorithms. We measured the impact of these techniques on the elapsed time to execute the algorithms, using C++ implementations with two different data representations, and using various data sets. The investigation also covers more basic transitive closure algorithms, and as a result forms a large-scale empirical comparison of such algorithms.

    Original languageEnglish
    Title of host publicationSAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    Pages1-10
    ISBN (Print)978-1-4503-5250-5
    DOIs
    Publication statusPublished - 26 Sep 2017
    Event2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017) - University of the Free State, Bloemfontein, South Africa
    Duration: 26 Sep 201728 Sep 2017
    Conference number: 23
    http://www.saicsit2017.org.za/

    Conference

    Conference2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017)
    Abbreviated titleSAICSIT 2017
    CountrySouth Africa
    CityBloemfontein
    Period26/09/1728/09/17
    Internet address

    Keywords

    • Algorithmic techniques
    • Benchmarking
    • Transitive closure

    Fingerprint Dive into the research topics of 'Benchmarking optimised algorithms for transitive closure'. Together they form a unique fingerprint.

    Cite this