IEICE TRANSACTIONS on Fundamentals
On the Computational Complexity of the Linear Solvability of Information Flow Problems with Hierarchy Constraint
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.12 pp.2211-2217
- Publication Date
- 2016/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.2211
- Type of Manuscript
- Special Section PAPER (Special Section on Information Theory and Its Applications)
- Category
- Networks and Network Coding
Authors
Yuki TAKEDA
Nara Institute of Science and Technology
Yuichi KAJI
Nara Institute of Science and Technology
Minoru ITO
Nara Institute of Science and Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yuki TAKEDA, Yuichi KAJI, Minoru ITO, "On the Computational Complexity of the Linear Solvability of Information Flow Problems with Hierarchy Constraint" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 12, pp. 2211-2217, December 2016, doi: 10.1587/transfun.E99.A.2211.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.2211/_p
Copy
@ARTICLE{e99-a_12_2211,
author={Yuki TAKEDA, Yuichi KAJI, Minoru ITO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Computational Complexity of the Linear Solvability of Information Flow Problems with Hierarchy Constraint},
year={2016},
volume={E99-A},
number={12},
pages={2211-2217},
abstract={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.},
keywords={},
doi={10.1587/transfun.E99.A.2211},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - On the Computational Complexity of the Linear Solvability of Information Flow Problems with Hierarchy Constraint
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2211
EP - 2217
AU - Yuki TAKEDA
AU - Yuichi KAJI
AU - Minoru ITO
PY - 2016
DO - 10.1587/transfun.E99.A.2211
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2016
AB - 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.
ER -
English
