I have a problem on distributed graph, with the following model:
1. There is a Global Graph $G=(V,E)$
2. There are $k$ computers.
3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph, i.e. $V$, and subset of the edges, i.e. computer $i$ knows $V_i \subseteq V$.
4. Each computer observes different subset of edges, i.e., for all $i,j$ : $V_i \cap V_j = \emptyset$.

I searched for papers which handle the same model, but I didn't find anything. Do you know if such model is being studied?

  • 3
    $\begingroup$ Should $V_i \subseteq V$ be $E_i \subseteq E$? Similarly, for part 4. $\endgroup$ Jan 10, 2016 at 15:24

1 Answer 1


The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"):

See also this work for closely related models:

You may also be interested in the "congested clique" model, which is the special case such that $k = |V|$ and computer number $i$ is aware of the edges incident to node number $i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.