Allerton 2015 Paper Abstract


Paper ThC4.4

Takeda, Yuki (Nara Institute of Science and Technology), Kaji, Yuichi (Nara Institute of Science and Technology), Ito, Minoru (Nara Institute of Science and Technology)

On the Computational Complexity of the Solvability of Information Flow Problem with Hierarchy Constraint

Scheduled for presentation during the Regular Session "Sensor Networks II" (ThC4), Thursday, October 1, 2015, 14:30−14:50, Pine

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on August 4, 2020

Keywords Network Coding, Network Coding in Communication


An information flow problem discusses how to transport 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 solvability of information flow problems, which is to decide if there is a linear network code that can be a solution to the given information flow problem. Lehman et al. characterize the 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 solvability of an information flow problem 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.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2020 PaperCept, Inc.
Page generated 2020-08-04  06:31:43 PST  Terms of use