Engineering a Topological Sorting Algorithm for Massive Graphs

Files in This Item:
File Description SizeFormat 
ajwani_alenex11.pdf1.21 MBAdobe PDFDownload
Title: Engineering a Topological Sorting Algorithm for Massive Graphs
Authors: Ajwani, Deepak
Cosgaya-Lozano, Adan
Zeh, Norbert
Permanent link: http://hdl.handle.net/10197/10513
Date: 1-Dec-2011
Online since: 2019-05-20T08:00:48Z
Abstract: We present an I/O-efficient algorithm for topologically sorting directed acyclic graphs (DAGs). No provably I/O-efficient algorithm for this problem is known. Similarly, the performance of our algorithm, which we call IterTS, may be poor in the worst case. However, our experiments show that IterTS achieves good performance in practise. The strategy of IterTS can be summarized as follows. We call an edge satisfied if its tail has a smaller number than its head. A numbering satisfying at least half the edges in the DAG is easy to find: A random numbering is expected to have this property. IterTS starts with such a numbering and then iteratively corrects the numbering to satisfy more and more edges until all edges are satisfied. To evaluate IterTS, we compared its running time to those of three competitors: PeelTS, an I/O-efficient implementation of the standard strategy of iteratively removing sources and sinks; ReachTS, an I/O-efficient implementation of a recent parallel divide-and-conquer algorithm based on reachability queries; and SeTS, standard DFS-based topological sorting built on top of a semi-external DFS algorithm. In our evaluation on various types of input graphs, IterTS consistently outperformed PeelTS and ReachTS, by at least an order of magnitude in most cases. SeTS outperformed IterTS on most graphs whose vertex sets fit in memory. However, IterTS often came close to the running time of SeTS on these inputs and, more importantly, SeTS was not able to process graphs whose vertex sets were beyond the size of main memory, while IterTS was able to process such inputs efficiently.
Type of material: Conference Publication
Publisher: Society for Industrial and Applied Mathematics
Copyright (published version): 2011 SIAM
Keywords: IterTSGraph algorithmsPeelTSReachTSVertex sets
DOI: 10.1137/1.9781611972917.14
Language: en
Status of Item: Not peer reviewed
Is part of: 2011 Proceedings of the 13th Workshop on Algorithm Engineering and Experiments, ALENEX 2011
Conference Details: ALEXNEX11: Workshop on Algorithm Engineering & Experiments, San Francisco, California, USA. 22 January 2011
Appears in Collections:Computer Science Research Collection

Show full item record

Google ScholarTM

Check

Altmetric


This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.