Brunel University Research Archive (BURA) >
Research Areas >
Information Systems and Computing >

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
Publication 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:Mathematics
Information Systems and Computing

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.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan