Please use this identifier to cite or link to this item:
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.
ISSN: 0166-218X
Appears in Collections:Computer Science
Mathematical Sciences

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.