Distance-Hereditary Graphs and Multidestination Message-Routing in Multicomputers

A graph \(G\) is istance-hereditary if for every connected induced subgraph \(H\) of \(G\) and every pair \(u,v\) of vertices of \(H\), we have \(d_H(u,v) = d_G(u,v)\). A frequently occurring communication problem in a multicomputer is to determine the most efficient way of routing a message from a processor (called the source) to a number of other processors (called the destinations). When devising a routing from a source to several destinations it is important that each destination receives the source message in a minimum number of time steps and that the total number of messages generated be minimized. Suppose \(G\) is the graph that models a multicomputer and let \(M = \{s, v_1, v_2, \ldots, v_k\}\) be a subset of \(V(G)\) such that \(s\) corresponds to the source node and the nodes \(v_1, v_2, \ldots, v_k\) correspond to the destinations nodes. Then an optimal communication tree (OCT) \(T\) for \(M\) is a tree that satisfies the following conditions:

1. \(M \subseteq V(T)\),
2. \(d_T(s, v_i) = d_G(s, v_i)\) for \(1 \leq i \leq k\),
3. no tree \(T’\) satisfying (a) and (b) has fewer vertices than \(T\).

It is known that the problem of finding an OCT is NP-hard for graphs \(G\) in general, and even in the case where \(G\) is the \(n\)-cube, or a graph whose maximum degree is at most three. In this article, it is shown that an OCT for a given set \(M\) in a distance-hereditary graph can be found in polynomial time. Moreover, the problem of finding the minimum number of edges in a distance-hereditary graph \(H\) that contains a given graph \(G\) as spanning subgraph is considered, where \(H\) is isomorphic to the \(n\)-cycle, the \(s\)-cube or the grid.