Downloads: 34

Files in This Item:
File Description SizeFormat 
mfeku_49_2_206.pdf464.38 kBAdobe PDFView/Open
Title: Graph Packing over a Rooted Tree
Authors: ZHANG, Ze-Zeng
MASUYAMA, Shigeru
IBARAKI, Toshihide
MINE, Hisashi
Issue Date: 28-May-1987
Publisher: Faculty of Engineering, Kyoto University
Journal title: Memoirs of the Faculty of Engineering, Kyoto University
Volume: 49
Issue: 2
Start page: 206
End page: 215
Abstract: 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 under two problem settings, 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. We first prove 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, we derive a recursive formula of dynamic programming 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 non-leaf node has the same number of sons. Furthermore, for GPT's with bins of uniform (d, H) trees and only one kind of item, of uniform (d, h) trees, we derive explicit formulas for the number of bins required.
URI: http://hdl.handle.net/2433/281352
Appears in Collections:Vol.49 Part 2

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.