Benchmarking optimised algorithms for transitive closure

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    1 Citaat (Scopus)

    Samenvatting

    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.

    Originele taal-2Engels
    TitelSAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa
    Plaats van productieNew York
    UitgeverijAssociation for Computing Machinery, Inc
    Pagina's1-10
    ISBN van geprinte versie978-1-4503-5250-5
    DOI's
    StatusGepubliceerd - 26 sep. 2017
    Evenement2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017) - University of the Free State, Bloemfontein, Zuid-Afrika
    Duur: 26 sep. 201728 sep. 2017
    Congresnummer: 23
    http://www.saicsit2017.org.za/

    Congres

    Congres2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017)
    Verkorte titelSAICSIT 2017
    Land/RegioZuid-Afrika
    StadBloemfontein
    Periode26/09/1728/09/17
    Internet adres

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Benchmarking optimised algorithms for transitive closure'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit