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

DOI10.1109/TIT.2011.2155618MaRDI QIDQ5272296zbMATH OpenOpenAlexFDO

Authors Maximilien Gadouleau, Søren Riis

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.2619

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Other game-theoretic models (91A40) Measures of information, entropy (94A17) Cyclic codes (94B15) Applications of graph theory to circuits and networks (94C15)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 1092008
• Source coding and graph entropies
• Graph theoretic methods in coding theory
• Graph connectivities, network coding, and expander graphs
• Mathematical foundations and applications of graph entropy
• Graph theoretic error-correcting codes
• Sierpinski gasket-based graphs in coding theory
• A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
• Dualities Between Entropy Functions and Network Codes

Cited in

(27)

• Fast depth-based subgraph kernels for unattributed graphs
• Positive and negative cycles in Boolean networks
• Expansive automata networks
• Hat problem: a new strategy based on quantum stabilizer codes
• Complexity of fixed point counting problems in Boolean networks
• Guessing numbers and extremal graph theory
• Hat guessing numbers of degenerate graphs
• On the stability and instability of finite dynamical systems with prescribed interaction graphs
• Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules
• Fixed points in conjunctive networks and maximal independent sets in graph contractions
• The linear guessing number of undirected graphs
• Bears with hats and independence polynomials
• Attractor separation and signed cycles in asynchronous Boolean networks
• Guessing games on triangle-free graphs
• Graph connectivities, network coding, and expander graphs
• Fixed points of Boolean networks, guessing graphs, and coding theory
• scientific article; zbMATH DE number 1092008 (Why is no real title available?)
• Finite dynamical systems, hat games, and coding theory
• Guessing numbers of odd cycles
• New constructions and bounds for Winkler's hat game
• Number of fixed points and disjoint cycles in monotone Boolean networks
• On the influence of the interaction graph on a finite dynamical system
• Complexity of limit cycles with block-sequential update schedules in conjunctive networks
• Bears with hats and independence polynomials
• Roots in the semiring of finite deterministic dynamical systems
• Injectivity of polynomials over finite discrete dynamical systems
• The hat guessing number of graphs

This page was built for publication: Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272296)