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}.$

The edge-bandwidth $B'(G)$ of a graph G is the bandwidth of the line graph of G. More specifically, for any bijection $f: E(G)\to \{1,2,\ldots, |E(G)|\}$, let $B'(f,G)=\max\{|f(e_1)- f(e_2)|: \mbox{$e1$ and $e2$ are incident edges of G}\}$, and let $B'(G)=\min_f B'(f,G)$. We determine asymptotically the edge-bandwidth of d-dimensional grids $P_n^d$ and of the Hamming graph $K_n^d$, the d-fold Cartesian product of $K_n$. Our results are as follows. (i) For fixed d and $n\to \infty$, $B'(P_n^d)=c(d)d n^{d-1}+O(n^{d-{3\over2}})$, where $c(d)$ is a constant depending on d, which we determine explicitly. (ii) For fixed even n and $d\to \infty$, $B'(K_n^d)=(1+o(1))\sqrt{d\over {2\pi}}\, n^d (n-1)$. Our results extend recent results by Balogh, Mubayi, and Pluhár [Theoret. Comput. Sci., 359 (2006), pp. 43–57], who determined $B'(P_n^2)$ asymptotically as a function of n and $B'(K_2^d)$ asymptotically as a function of d.

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

Abstract Let G be a graph, and denote by Q(G)/2t the hypercube of dimension ⌈log2|G|⌉ − t. Motivated by the problem of simulating large grids by small hypercubes, we construct maps f:G → Q(G)/2t, t ⩾ 1, when G is any 2‐ or 3‐dimensional grid, with a view to minimizing communication delay and optimizing distribution of G‐processors in Q(G)/2t, Let dilation(f) = max {dist(f(x), f(y)): xyε(G)}, where “dist” denotes distance in the image network Q(G)/2t, and let the load factor of f be the maximum value of >f−1(h)| over all vertices hε(G)/2t. Our main results are the following: (1) Let G be any 2‐dimensional grid. Then, for any t ⩾ 1, there is a map f :G → Q(G)/2t having dilation 1 and load factor at most 1 + 2t. (2) Given certain upper bounds on the “densities” |G|/|Q(G)/4| or |G|/|Q(G)/8| of G in Q(G)/4 or Q(G)/8, respectively, we get dilation 1 maps f:G → Q(G)/4 or f:G → Q(G)/8 with improved (i.e., smaller) load factor over that given in (1). (3) Let G be any 3‐dimensional grid. Then, there is a map f:G → Q(G)/2 of dilation at most 2 and load factor at most 3, and a map f:G → Q(G)/4 of dilation at most 3 and load factor at most 5.

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 Let Q ( n ) be the n ‐dimensional hypercube, and X , a set of points in Q ( n ). The Steiner problem for the hypercube is to find the smallest possible number L ( n,X ) of edges in any subtree of Q ( n ) that spans X . We obtain the following results: An exact formula for L ( n,X ), when | X | ≤ 5. The bound L ( n,X ) ≤ ( n k +1 ) + (2 + o (1)) ([log ( k )]/ k )( n k ) as k → ∞, when X is the set of all points in Q ( n ) of a given weight k + 1, provided ( k 2 /[log ( k )]) 1 + 1/ k ≤ n . NP‐completeness of deciding L ( n,X ) even when every point of X has weight at most 2.

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.

Let G be a graph, and f a one-to-one map of G into the positive integers. The bandwidth ofG is $B(G) = \min _f \max \{ {|f(x) - f(y)|:xy \in E(G)} \}$, where the max is taken over all edges $xy$ in G and the min over all maps f. $B(G)$ is related to the matrix bandwidth $B(M)$ for a symmetric matrix M, and knowledge of the latter parameter is important for the efficient execution of certain matrix operations. The problem of determining $B(G)$ for arbitrary G was shown by Papadimitriou to be NP-complete, and it was subsequently proved NP-complete even when $G \in \Omega $, where $\Omega $ is the set of trees with maximum degree 3. Let $B^ * (G)$ be the minimum possible bandwidth of any subdivision of G, i.e., any graph obtained from G by inserting degree-2 points along edges of G. We present an $O(n)$ algorithm for computing $B^ * (G)$ when $G \in \Omega $.

A problem arising in the design of vacuum systems and having applications to some natural problems of interconnection design is described as follows. (1) Given a set X and subsets $X_i ,Y_i $ of $X,i = 1, \cdots ,n$, satisfying $X_i \cap Y_i = \O $, find a graph G with vertex set X and the minimum number of edges such that for any i, the subgraph induced by $X\backslash Y_i $ has a connected component containing $X_i $. Two other problems related to this one are the following ones. (2) Given a set X and subsets $X_1 ,X_2 , \cdots ,X_n $ such that $X = \cup _{i = 1}^n X_i $, find a graph G with vertex set X and the minimum number of edges such that for any i the subgraph $G_i $ induced by $X_i $ in G is connected. (3) Given a set X and subsets $X_1 ,X_2 , \cdots ,X_n $ such that $X = \cup _{i = 1}^n X_i $, find a graph G with vertex set X, find a graph G with vertex set X and the minimum number of edges such that for any subset I of $\{ 1, \cdots ,n \}$, the subgraph induced by $ \cap _{i \in I} X_i $ is connected. This paper shows that (3) is polynomial-time solvable while (1) and (2) are NP-complete. Also, some heuristics for (1) and (2) are given. The solution of (3) is an interesting application of matroid theory.