Efficient Embedding of Functions in Weighted Communication Networks.

摘要: We consider the problem of efficient distributed computation arbitrary function on communication network. The algorithm to compute is given by graph $\mathcal{G}$ which represented weighted directed acyclic (DAG) and network a $\mathcal{N}.$ two variations problem. First we minimizing delay computing function. prove that NP-hard when DAG arbitrary. give an solves this tree structured in $O(pn^2)$ time where $p$ $n$ are number vertices $\mathcal{N},$ respectively. Then looked at cost also for graph. There many polynomial-time algorithms available literature tree. layered takes $O(rn^{2k})$ $r$ layers $k$ maximum any layer.