×

Distance-hereditary graphs and multidestination message-routing in multicomputers. (English) Zbl 0776.68093

A graph \(G\) is distance-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 received 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:
(a) \(M\subseteq V(T)\),
(b) \(d_ T(s,v_ i)=d_ G(s,v_ i)\) for \(1\leq i\leq k\),
(c) 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\) is general, and even in the case where \(G\) is the \(n\)-cube, or a graph whose maximum degree is at most three.
It is shown that 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 \(n\)-cube or the grid.
Reviewer: A.-H.Esfahanian

MSC:

68R10 Graph theory (including graph drawing) in computer science
68M10 Network design and communication in computer systems
68Q25 Analysis of algorithms and problem complexity
05C12 Distance in graphs
PDFBibTeX XMLCite