Given a set S of vertices in a connected graph G, the classic Steiner tree problem asks for the minimum number of edges of a connected subgraph of G that contains S. We study this problem in the hypercube. Given a set S of vertices in the n-dimensional hypercube $Q_n$, the Steiner cost of S, denoted by $cost(S)$, is the minimum number of edges among all connected subgraphs of $Q_n$ that contain S. We obtain the following results on $cost(S)$. Let $\epsilon$ be any given small, positive constant, and set $k=|S|$. (1) [upper bound] For every set S we have $cost(S) < (\frac{1}{3}k + 1 + \frac{1}{2}\ln k)n.$ In particular, there is a constant $c_1$ depending only on $\epsilon$ such that if $k > c_1$, then $cost(S) < (\frac{1}{3} + \epsilon)kn.$ (2) We develop a randomized algorithm of running time $O(kn)$ that produces a connected subgraph H of $Q_n$ containing S such that with probability approaching 1 as $k,n\to\infty$ we have $|E(H)| < (\frac{1}{3} + \epsilon)kn$. (3) [lower bound] There are constants $c_2$ and b (with $1 (\frac{1}{3} - \epsilon)kn$. Thus for k in this range with $k\to \infty$, the upper bound (1) is asymptotically tight. We also show that for fixed k, as $n\to \infty$, almost always a random family of k vertices in $Q_n$ satisfies $[\frac{k}{3}+\frac{2}{9}(-1+(-\frac{1}{2})^k)] n - \sqrt{n\ln n}\leq cost (S)\leq [\frac{k}{3}+\frac{2}{9}(-1+(-\frac{1}{2})^k)] n + \sqrt{n\ln n}.$

Abstract This article is motivated by versions of the dynamic or “on‐line” Steiner tree problem (OST) introduced by Imase and Waxman [ 4 ]. In this problem one is given an edge‐weighted graph G and a sequence σ = (x1,…,xn) of distinct vertices of G. The requirement is to construct for each i ≤ n a tree Ti spanning the first i vertices of σ subject to the condition that Ti−1⫅Ti for all i, where Ti is constructed without knowledge of the remaining vertices xj, j > i. The goal of the on‐line Steiner problem is to minimize the performance ratio; that is, the maximum (over 1 ≤ i ≤ n) of the ratio of the weight of Ti to the weight of the minimum weight tree in G spanning the first i vertices (the latter tree is called the “Steiner tree” for these vertices). In [ 4 ] a lower bound of 1 + ½⌊ log2(n−1)⌋ was proved for this ratio. The authors further made the interesting conjecture that there is some on‐line algorithm for the OST whose performance ratio achieves this lower bound. We show that a strong form of the greedy algorithm achieves a ratio that converges to the conjectured ½log2(k) + O(1) as the proportion of degree 2 vertices in the instance graph grows. Our results also imply improvements in certain cases on the known upper bound ⌈log2(n)⌉ for the performance ratio of the greedy algorithm. Our approach is to study a related graph parameter. For each sequence σ as above, define the associated cost where c(i,σ) = min1 ≤ t < idist(xi, xt). Then let Opt(n, G) be the maximum of L(σ) over all such sequences σ of length n. The problem of, given n and G, determining Opt(n, G) we call the Sequential Sum Problem (SSP). In this article we analyze the SSP, obtaining exact values and bounds on Opt(n, G) and relating these bounds to the greedy algorithm for the OST. For example, we calculate Opt(n, P) for the path P, and obtain a surprising characterization of all length n sequences σ which realize Opt(n, P). By analyzing Opt(n, P) for the “continuous” path, we derive upper bounds on the performance ratio of the greedy algorithm for the OST in arbitrary graphs. On the other hand, generalizing the lower bound argument of [ 4 ] we show that there are instances of OST, which can significantly “fool” any on‐line algorithm for OST. Specifically, given any tree T normalized to have total edge weight 1, we construct a graph G and a length k ≤ |V(T)| sequence σ of vertices of G for which the performance ratio of any on‐line algorithm for the OST with input σ is lower bounded by Opt(k, T). Finally, we show that the SSP for arbitrary G is NP‐complete. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 143–164 2005

Simulations of hypercube networks by certain Cayley graphs on the symmetric group are investigated. Let Q(k) be the familiar k-dimensional hypercube, and let S(n) be the star network of dimension n defined as follows. The vertices of S(n) are the elements of the symmetric group of degree n, two vertices x and y being adjacent if xo(1,i)=y for some i. That is, xy is an edge if x and y are related by a transposition involving some fixed symbol (which we take to be /spl I.bold/1). This network has nice symmetry properties, and its degree and diameter are sublogarithmic as functions of the number of vertices, making it compare favorably with the hypercube network. These advantages of S(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hypercube. The first step in such a simulation is the construction of a one-to-one map f:Q(k)/spl rarr/S(n) of dilation d, for d small. That is, one wants a map f such that images of adjacent points are at most distance d apart in S(n). An alternative approach, best applicable when one-to-one maps are difficult or impossible to find, is the construction of a one-to-many map g of dilation d, defined as follows. For each point x/spl isin/Q(k), there is an associated subset g(x)/spl sube/V(S(n)) such that for each edge xy in Q(k), every x'/spl isin/g(x) is at most distance d in S(n) from some y'/spl isin/g(y). Such one-to-many maps allow one to achieve the low interprocessor communication time desired in the usual one-to-one embedding underlying a simulation. This is done by capturing the local structure of Q(k) inside of S(n) (via the one-to-many embedding) when the global structure cannot be so captured. Our results are the following. 1) There exist the following one-to-many embeddings: a) f:Q(k)/spl rarr/S(3k+1) with dilation (f)=1; b) f:Q(11k+2)/spl rarr/S(13k+2) with dilation (f)=2. 2) There exists a one-to-one embedding f:Q(n2/sup n/spl minus/1/)/spl rarr/S(2/sup n/) with dilation (f)=3.>

Abstract We consider the following graph labeling problem, introduced by Leung et al. (J. Y‐T. Leung, O. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem. SIAM J. Comput . 13 (1984) 650–667). Let G be a graph of order n , and f a bijection from V(G) to the integers 1 through n. Let |f|, and define s ( G ), the separation number of G , to be the maximum of |f| among all such bijections f . We first derive some basic relations between s ( G ) and other graph parameters. Using a general strategy for analyzing separation number in bipartite graphs, we obtain exact values for certain classes of forests and asymptotically optimal lower bounds for grids and hypercubes.