GRAPH PACKING OVER A ROOTED TREE.

被引：0

作者：

Zhang, Ze-Zeng ^{[1
]}

Masuyama, Shigeru ^{[1
]}

Ibaraki, Toshihide ^{[1
]}

Mine, Hisashi ^{[1
]}

机构：

[1] Xibei Inst of Telecommunication, Engineering, Xian, China, Xibei Inst of Telecommunication Engineering, Xian, China

来源：

Memoirs of the Faculty of Engineering, Kyoto University | 1987年 / 49卷 / pt 2期

关键词：

DECISION THEORY AND ANALYSIS - MATHEMATICAL PROGRAMMING; DYNAMIC - Mathematical Models;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

This paper investigates the computational complexity of the graph packing problem over a rooted tree (GPT) as a generalization of the one-dimensional bin packing problem, where both the bins and the set of items to be packed are rooted trees. GPT is defined for two problem formulations, edge GPT (EPT) and node GPT (NPT). In EPT, the items packed in a bin cannot share any edge but can share some node, while in NPT the items can share neither node nor edge. It is proven that these problems are in general NP-complete, which strongly suggests that these problems are computationally intractable. However, for the case where the number k of different kinds of items is fixed the authors derive a recursive dynamic programming formula for the minimum number of bins required to pack all the items. This formula can be solved in polynomial time, if the bins and items are all uniform trees and/or comb-shaped trees in which each nonleaf parent node has the same number of sons.

引用

页码：206 / 215