The Complexity of the Node Capacitated In-Tree Packing Problem
The Complexity of the Node Capacitated In-Tree Packing Problem
复制标题
节点容量树内填充问题的复杂性
DOI：
10.1002/net.20476
复制
发表时间：
2012
期刊：
影响因子：
2.1
通讯作者：
Mutsunori Yagiura
中科院分区：
文献类型：
--
作者：
Shinji Imahori;Yuichiro Miyamoto;Hideki Hashimoto;Yusuke Kobayashi;Mihiro Sasaki;Mutsunori Yagiura
这篇文章描述了一个节点容量受限的入树装箱问题。输入由有向图、根节点、节点容量函数和边消耗函数组成。问题是找到最大数量的根入树，使得每个节点上的入树的总消耗不超过节点的容量。该问题是传感器网络中最重要的问题之一，网络寿命问题。我们建立了各种限制下的消费函数和图形的问题的计算复杂性。例如，我们考虑一般图，无环图和完全图嵌入在th-dimensional空间\input amssym中，其边消耗函数仅取决于端节点之间的距离。© 2011 Wiley Periodicals，Inc.网络，2012年
This article describes a node capacitated in‐tree packing problem. The input consists of a directed graph, a root node, a node capacity function, and edge consumption functions. The problem is to find the maximum number of rooted in‐trees, such that the total consumption of in‐trees at each node does not exceed the capacity of the node. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We establish the computational complexity of the problem under various restrictions on consumption functions and graphs. For example, we consider general graphs, acyclic graphs, and complete graphs embedded in thed‐dimensional space \input amssymhaving edge consumption functions depending only on distances between end nodes. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012