A Graph Theoretical Approach to Network Encoding Complexity

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

44 pages, 22 figures

Scientific paper

Consider an acyclic directed network $G$ with sources $S_1, S_2,..., S_l$ and distinct sinks $R_1, R_2,..., R_l$. For $i=1, 2,..., l$, let $c_i$ denote the min-cut between $S_i$ and $R_i$. Then, by Menger's theorem, there exists a group of $c_i$ edge-disjoint paths from $S_i$ to $R_i$, which will be referred to as a group of Menger's paths from $S_i$ to $R_i$ in this paper. Although within the same group they are edge-disjoint, the Menger's paths from different groups may have to merge with each other. It is known that by choosing Menger's paths appropriately, the number of mergings among different groups of Menger's paths is always bounded by a constant, which is independent of the size and the topology of $G$. The tightest such constant for the all the above-mentioned networks is denoted by $\mathcal{M}(c_1, c_2,..., c_2)$ when all $S_i$'s are distinct, and by $\mathcal{M}^*(c_1, c_2,..., c_2)$ when all $S_i$'s are in fact identical. It turns out that $\mathcal{M}$ and $\mathcal{M}^*$ are closely related to the network encoding complexity for a variety of networks, such as multicast networks, two-way networks and networks with multiple sessions of unicast. Using this connection, we compute in this paper some exact values and bounds in network encoding complexity using a graph theoretical approach.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

A Graph Theoretical Approach to Network Encoding Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Graph Theoretical Approach to Network Encoding Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Graph Theoretical Approach to Network Encoding Complexity will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-5265

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.