Premium
The complexity of the node capacitated in‐tree packing problem
Author(s) -
Imahori Shinji,
Miyamoto Yuichiro,
Hashimoto Hideki,
Kobayashi Yusuke,
Sasaki Mihiro,
Yagiura Mutsunori
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20476
Subject(s) - node (physics) , computer science , tree (set theory) , enhanced data rates for gsm evolution , context (archaeology) , directed acyclic graph , mathematics , computational complexity theory , graph , combinatorics , mathematical optimization , theoretical computer science , algorithm , telecommunications , paleontology , structural engineering , engineering , biology
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 the d ‐dimensional space \input amssym ${\Bbb{R}}^d$ having edge consumption functions depending only on distances between end nodes. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012