IEEE - Institute of Electrical and Electronics Engineers, Inc. - Lower Bounds for Testing Digraph Connectivity with One-Pass Streaming Algorithms

Author(s): Theresa Migler
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 January 2018
Volume: 1
Page(s): 9 - 11
ISSN (Electronic): 2573-9689
DOI: 10.1109/LCOS.2018.2854761
Regular:

In this note, we show that three graph properties-strong connectivity, acyclicity, and reachability from a vertex s to all vertices-each require a working memory of Ω(εm) on a graph with... View More

Advertisement