English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider directed graph algorithms in a streaming setting, focusing onproblems concerning orderings of the vertices. This includes such fundamentalproblems as topological sorting and acyclicity testing. We also study therelated problems of finding a minimum feedback arc set (edges whose removalyields an acyclic graph), and finding a sink vertex. We are interested in bothadversarially-ordered and randomly-ordered streams. For arbitrary input graphswith edges ordered adversarially, we show that most of these problems have highspace complexity, precluding sublinear-space solutions. Some lower bounds alsoapply when the stream is randomly ordered: e.g., in our most technical resultwe show that testing acyclicity in the $p$-pass random-order model requiresroughly $n^{1+1/p}$ space. For other problems, random ordering can make adramatic difference: e.g., it is possible to find a sink in an acyclictournament in the one-pass random-order model using polylog$(n)$ space whereasunder adversarial ordering roughly $n^{1/p}$ space is necessary and sufficientgiven $\Theta(p)$ passes. We also design sublinear algorithms for the feedbackarc set problem in tournament graphs; for random graphs; and for randomlyordered streams. In some cases, we give lower bounds establishing that ouralgorithms are essentially space-optimal. Together, our results complement themuch maturer body of work on algorithms for undirected graph streams.

Vertex Ordering Problems in Directed Graph Streams