Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

I/O-Efficient Algorithms for Topological Sort and Related Problems

I/O-Efficient Algorithms for Topological Sort and Related Problems This article presents I/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graph G = (V, E). Both algorithms are randomized and have I/O-costs O(sort(E) · poly(log V)), with high probability, where sort(E) = O(E/B log M/B(E/B)) is the I/O cost of sorting an |E|-element array on a machine with size-B blocks and size-M cache/internal memory. These are the first algorithms for these problems that do not incur at least one I/O per vertex, and as such these are the first I/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

I/O-Efficient Algorithms for Topological Sort and Related Problems

Download PDF
24 pages

Loading next page...
 
/lp/association-for-computing-machinery/i-o-efficient-algorithms-for-topological-sort-and-related-problems-kFIQTEEV1v
Publisher
Association for Computing Machinery
Copyright
Copyright © 2022 Association for Computing Machinery.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3418356
Publisher site
See Article on Publisher Site

Abstract

This article presents I/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graph G = (V, E). Both algorithms are randomized and have I/O-costs O(sort(E) · poly(log V)), with high probability, where sort(E) = O(E/B log M/B(E/B)) is the I/O cost of sorting an |E|-element array on a machine with size-B blocks and size-M cache/internal memory. These are the first algorithms for these problems that do not incur at least one I/O per vertex, and as such these are the first I/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Jan 22, 2022

Keywords: I/O efficient

References

  • A functional approach to external graph algorithms
    [,
  • The input/output complexity of sorting and related problems
    [,
  • Engineering a topological sorting algorithm for massive graphs
    [,
  • The buffer tree: A new technique for optimal I/O-algorithms
    [,
  • On external-memory MST, SSSP and multi-way planar graph separation
    [,
  • External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs
    [,
  • I/O-efficient contour tree simplification
    [,
  • I/O-efficient topological sorting of planar DAGs
    [,
  • On external memory graph traversal
    [,
  • External-memory graph algorithms
    [,
  • External-memory exact and approximate all-pairs shortest-paths in undirected graphs
    [,
  • A labeling approach to incremental cycle detection
    [,
  • A Divide-and-Conquer Algorithm for Identifying Strongly Connected Components
    [,
  • Introduction to Algorithms (2nd ed
    [,
  • Sparsification—A technique for speeding up dynamic graph algorithms
    [,
  • Nearly work-efficient parallel algorithm for digraph reachability
    [,
  • Efficient external-memory bisimulation on DAGs
    [,
  • Improved algorithms and data structures for solving graph problems in external memory
    [,
  • I/O-efficient planar separators
    [,
  • External-memory breadth-first search with sublinear I/O
    [,
  • I/O-efficient undirected shortest paths
    [,
  • I/O-efficient undirected shortest paths with unbounded edge lengths
    [,
  • I/O-complexity of graph algorithms
    [,
  • Depth first search and linear graph algorithms
    [,
  • The input/output complexity of transitive closure
    [,
  • Algorithms and data structures for external memory
    [,
  • [n
    [,
  • I/O efficient: Computing SCCs in massive graphs
    [,