Optimal arrangement of data in a tree directory [Discrete Appl. Math 113 (2001) 243-253]

摘要

We define the decision problem 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 data arrangement is strongly NP-complete for any fixed d ≥ 2 and explain the connection between data arrangement and arranging data in a particular form of distributed directory.