Network - Coded Multihop Multicast: Topology and Complexity

In this section we analyze the complexity, in terms of required elementary operations, of the algorithm performed in order to find CP. The procedure generating the random graph G has a complexity on the order of O(n2).

In fact, for each vertex of A other n-1 vertices are analyzed in order to generate a random topology.
Moreover, the runtime of the Ford-Fulkerson algorithm is bounded by O(|E|hk), where jEj is the number (which can be approximately compared to n2) of edges in graph G. The minimality graph algorithm, instead, has a runtime bounded by O(n2|E|hk), since we have to analyze each edge (i; j) and run every time the Ford-Fulkerson algorithm for each receiver node in order to find out which edges in the network can be eliminated without affecting the min-cut.

Noting that |E| = O(n2), we can approximately state that the minimality check has an order of O(n4hk). Finally, the generation of has a complexity on the order of O(n2 min), where nmin is equal to the number of elements in A ϒ. In fact, each node in Gmin is analyzed in order to identify all the outgoing edges from it. This order of complexity can be approximated with the corresponding order of the generating random graph algoritm; therefore, we can assume n2min ∼ n2, especially for networks with larger values of h and consequently a greater number of survivor nodes in Gmin.