Downloads: 34
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
mfeku_49_2_206.pdf | 464.38 kB | Adobe PDF | View/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 |

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