Esfahanian, Abdol-Hossein; Oellermann, Ortrud R. Distance-hereditary graphs and multidestination message-routing in multicomputers. (English) Zbl 0776.68093 J. Comb. Math. Comb. Comput. 13, 213-222 (1993). 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 Cited in 1 ReviewCited in 7 Documents 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 Keywords:communication; multicomputer; routing; optimal communication tree; NP- hard; distance-hereditary graph PDFBibTeX XMLCite \textit{A.-H. Esfahanian} and \textit{O. R. Oellermann}, J. Comb. Math. Comb. Comput. 13, 213--222 (1993; Zbl 0776.68093)