3
$\begingroup$

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?

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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