We investigate the arithmetic-geometric structure of the lecture hall cone $L_n \ := \ \big\{\lambda\in \mathbb{R}^n: \, 0\leq \frac{\lambda_1}{1}\leq \frac{\lambda_2}{2}\leq \frac{\lambda_3}{3}\leq \cdots \leq \frac{\lambda_n}{n}\big\}$. We show that $L_n$ is isomorphic to the cone over the lattice pyramid of a reflexive simplex whose Ehrhart $h^*$-polynomial is given by the $(n-1)$st Eulerian polynomial and prove that lecture hall cones admit regular, flag, unimodular triangulations. After explicitly describing the Hilbert basis for $L_n$, we conclude with observations and a conjecture regarding the structure of unimodular triangulations of $L_n$, including connections between enumerative and algebraic properties of $L_n$ and cones over unit cubes.

Wavelength converters simplify the wavelength assignment problem in virtual topology design in optical networks and increase the utilization of the fiber bandwidth. However, converters are costly, and minimizing the number of converters needed to support a given level of functionality has been investigated in the literature in various contexts. In particular, previous work has addressed the problem of minimizing the number of converters needed to support broadcast over all network nodes with a given set of residual wavelengths on each link. In this paper, we show that previous work leaves the computational complexity of this question open. We go on to show that the problem is in fact NP-complete, but becomes tractable in the special case when the network graph is a tree. We also show that there are cases when the heuristics articulated in previous work fail to provide solutions, and provide some heuristic approaches to solve the general problem.

In this paper we study the following question posed by H. S. Wilf: what is, asymptotically as $n\rightarrow \infty$, the probability that a randomly chosen part size in a random composition of an integer n has multiplicity m? More specifically, given positive integers n and m, suppose that a composition $\lambda$ of n is selected uniformly at random and then, out of the set of part sizes in $\lambda$, a part size j is chosen uniformly at random. Let $\P(A_n^{(m)})$ be the probability that j has multiplicity m. We show that for fixed m, $\P(A_n^{(m)}$) goes to 0 at the rate $1/\ln n$. A more careful analysis uncovers an unexpected result: $(\ln n)\P(A_n^{(m)})$ does not have a limit but instead oscillates around the value $1/m$ as $n\to\infty$. This work is a counterpart of a recent paper of Corteel, Pittel, Savage, and Wilf, who studied the same problem in the case of partitions rather than compositions.

A necklace is an equivalence class of binary strings under rotation. In this paper, we present a Gray code listing of all n-bit necklaces with d ones so that (i) each necklace is listed exactly once by a representative from its equivalence class and (ii) successive representatives, including the last and the first in the list, differ only by the transposition of two bits. The total time required is ${\text{O}}(nN(n,d))$, where $N(n,d)$ denotes the number of n-bit binary necklaces with d ones. This is the first algorithm for generating necklaces of fixed density which is known to achieve this time bound.

Let B be a basis of transpositions for $S_n $ and let Cay$( B:S_n )$ be the Cayley graph of $S_n $ with respect to B. It was shown by Kompel’makher and Liskovets [Kibemetica, 3 (1975), pp. 17–21] that Cay$( B:S_n )$ is Hamiltonian. This result is extended as follows. Note that every transposition b in B induces a perfect matching $M_b $ in Cay$( B:S_n )$. It is shown here when $n > 4$ that, for any $b \in B$, there is a Hamilton cycle in Cay$( B:S_n )$ that includes every edge of $M_b $. That is, for $n > 4$, for any basis B of transpositions of $S_n $, and, for any $b \in B$, it is possible to generate all permutations of $1,2, \ldots ,n$ by transpositions in B so that every other transposition is b.

Given $( n,k )$ with $n\geqq k\geqq 2$ and $k \ne 3$, it is shown how to generate all permutations of n objects (each exactly once) so that successive permutations differ in exactly k positions, as do the first and last permutations. This solution generalizes known results for the specific cases where $k = 2$ and $k = n$. It is shown that it is possible, when $k = 3$, to generate all even (odd) permutations of n objects so that successive permutations differ in exactly three positions.

We show how tree structures can be embedded in a one-dimensional systolic array to solve a connectivity problem, the UNION-FIND problem, by a single left-to-right pass of the data through the array. A previous solution, which did not use trees, required a left-to-right pass followed by a right-to-left pass through the array, as well as a more complex program for each cell.

In this paper we present a design, suited to VLSI implementation, for a one-dimensional array to solve graph connectivity problems. The computational model is relatively primitive in that only the two end cells of the array can interact with the external environment and only adjacent cells in the array are allowed to communicate. However, we show that an array of n + 1 cells can be used for a graph with n vertices to find the connected components, a spanning tree, or, when used in conjunction with a systolic priority queue, a minimum spanning tree. The area, time, and I/O requirements compare favorably with other models proposed for this problem in the case of sparse graphs.

Two common problems in image analysis are described—the region-labeling problem and the clustering problem. Both are shown to be instances of a search-and-rename problem which can be solved in parallel by a system architecture inherently suitable for VLSI implementation.

Algorithms for solving graph problems on an unbounded parallel model of computation are considered. Parallel algorithms of time complexity $O(\log ^2 n)$ are described for finding biconnected components, bridges, minimum spanning trees and fundamental cycles. In the algorithms for finding minimum spanning trees, bridges, and fundamental cycles, the number of processors used is small enough that the parallel algorithm is efficient in comparison with the best sequential algorithms for these problems. Several other algorithms are presented which are especially suitable for processing sparse graphs.