Engineering a Topological Sorting Algorithm for Massive Graphs
|Title:||Engineering a Topological Sorting Algorithm for Massive Graphs||Authors:||Ajwani, Deepak
|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:||IterTS; Graph algorithms; PeelTS; ReachTS; Vertex 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
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.