Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/1676
Title: | Optimal arrangement of data in a tree directory |
Authors: | Luczak, M J Noble, S D |
Keywords: | Complexity;Graph embedding;Data arrangement |
Issue Date: | 2002 |
Publisher: | Elsevier |
Citation: | Discrete Applied Mathematics, 121(1-3): 307-315, Sep 2002 |
Abstract: | We define the decision problem {\textsc {data arrangement}}, which involves arranging the vertices of a graph $G$ at the leaves of a $d$-ary tree so that a weighted sum of the distances between pairs of vertices measured with respect to the tree topology is at most a given value. We show that {\textsc{data arrangement}} is strongly NP-complete for any fixed $d \ge 2$ and explain the connection between {\textsc{data arrangement}} and arranging data in a particular form of distributed directory. |
URI: | http://bura.brunel.ac.uk/handle/2438/1676 |
DOI: | http://dx.doi.org/10.1016/S0166-218X(01)00174-3 |
ISSN: | 0166-218X |
Appears in Collections: | Computer Science Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
revsubitted.pdf | 153.86 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.