Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Submitted to IEEE Transactions on Information Theory

Scientific paper

The guessing number of a directed graph (digraph), equivalent to the entropy of that digraph, was introduced as a direct criterion on the solvability of a network coding instance. This paper makes two contributions on the guessing number. First, we introduce an undirected graph on all possible configurations of the digraph, referred to as the guessing graph, which encapsulates the essence of dependence amongst configurations. We prove that the guessing number of a digraph is equal to the logarithm of the independence number of its guessing graph. Therefore, network coding solvability is no more a problem on the operations made by each node, but is simplified into a problem on the messages that can transit through the network. By studying the guessing graph of a given digraph, and how to combine digraphs or alphabets, we are thus able to derive bounds on the guessing number of digraphs. Second, we construct specific digraphs with high guessing numbers, yielding network coding instances where a large amount of information can transit. We first propose a construction of digraphs with finite parameters based on cyclic codes, with guessing number equal to the degree of the generator polynomial. We then construct an infinite class of digraphs with arbitrary girth for which the ratio between the linear guessing number and the number of vertices tends to one, despite these digraphs being arbitrarily sparse. These constructions yield solvable network coding instances with a relatively small number of intermediate nodes for which the node operations are known and linear, although these instances are sparse and the sources are arbitrarily far from their corresponding sinks.

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

Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications 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-theoretical Constructions for Graph Entropy and Network Coding Based Communications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-226438

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