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:Mathematical Science
Computer Science

Files in This Item:
File Description SizeFormat 
revsubitted.pdf153.86 kBAdobe PDFView/Open


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