data-streams streaming: Updated Wed, 22 Jun 2022 05:19:04 GMT

"Computing on data streams" clarification

In the 1998 technical note "Computing on data streams" by Monika Rauch Henzinger , Prabhakar Raghavan , Sridar Rajagopalan (found here: http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf)

They define a directed multigraph with node set V1 union V2 union union Vk, all of whose edges are directed from a node in Vi to a node in Vi+1.

I cannot see how this allows for disconnected components? Can anyone clarify this?

Solution

The definition says that every edge that exists has to go from some $V_i$ to $V_{i+1}$. It doesn't say that every possible edge from $V_i$ to $V_{i+1}$ has to be there. For example, $V_1=\{a,b\}$, $V_2=\{c,d\}$ with edges $ac$ and $bd$ gives a disconnected graph.

External Links

External links referenced by this document:

http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf

References

https://cstheory.stackexchange.com/questions/18582