Mathematics – Combinatorics
Scientific paper
2007-11-27
Mathematics
Combinatorics
30 pages, 3 figures
Scientific paper
We introduce the (private) entropy of a directed graph (in a new network coding sense) as well as a number of related concepts. We show that the entropy of a directed graph is identical to its guessing number and can be bounded from below with the number of vertices minus the size of the graph's shortest index code. We show that the Network Coding solvability of each specific multiple unicast network is completely determined by the entropy (as well as by the shortest index code) of the directed graph that occur by identifying each source node with each corresponding target node. Shannon's information inequalities can be used to calculate upper bounds on a graph's entropy as well as calculating the size of the minimal index code. Recently, a number of new families of so-called non-shannon-type information inequalities have been discovered. It has been shown that there exist communication networks with a capacity strictly less than required for solvability, but where this fact cannot be derived using Shannon's classical information inequalities. Based on this result we show that there exist graphs with an entropy that cannot be calculated using only Shannon's classical information inequalities, and show that better estimate can be obtained by use of certain non-shannon-type information inequalities.
No associations
LandOfFree
Graph Entropy, Network Coding and Guessing games 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 Graph Entropy, Network Coding and Guessing games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Entropy, Network Coding and Guessing games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-685938