For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Computational Complexity of the Linear Solvability of Information Flow Problems with Hierarchy Constraint
Yuki TAKEDA Yuichi KAJI Minoru ITO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/12/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Networks and Network Coding
information flow problem, network coding, computational complexity, hierarchy constraint, mesh network,
Full Text: PDF(636.3KB)>>
An information flow problem is a graph-theoretical formalization of the transportation of information over a complicated network. It is known that a linear network code plays an essential role in a certain type of information flow problems, but it is not understood clearly how contributing linear network codes are for other types of information flow problems. One basic problem concerning this aspect is the linear solvability of information flow problems, which is to decide if there is a linear network code that is a solution to the given information flow problem. Lehman et al. characterize the linear solvability of information flow problems in terms of constraints on the sets of source and sink nodes. As an extension of Lehman's investigation, this study introduces a hierarchy constraint of messages, and discusses the computational complexity of the linear solvability of information flow problems with the hierarchy constraints. Nine classes of problems are newly defined, and classified to one of three categories that were discovered by Lehman et al.