Distance-Hereditary Graphs and Multidestination Message-Routing in Multicomputers

Abstract

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,\dots ,v_k\}$ be a subset of $V(G)$ such that $s$ corresponds to the source node and the nodes $v_1,v_2,\dots ,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\le i\le k$,
3. no tree $T^{\prime }$ 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.