Binary tree structures have been very useful in solving divide-and-conquer type of problems. Embedding binary trees into another network-the host network-helps in designing solutions for the host network using the known solutions on binary trees. Embedding arbitrary binary trees into networks, in particular into the hypercube, has been addressed in the literature. The latter was achieved with load 1 and constant dilation. The n-star graph is a recently introduced interconnection network for massively parallel systems. It enjoys symmetry and fault tolerance properties that make it a viable alternative to the hypercube. In this paper, we address the problem of embedding arbitrary binary trees into the n-star graph. This work is the first to present such an embedding. The tree has [e(n-1)1] or fewer vertices. The embedding leads to load 1 and constant dilation for all values of n. It therefore enables the star graph to efficiently simulate an arbitrary binary tree with only a constant factor of communication delay.

An enumeration of star graphs is given which has many useful properties. For example an arbitrary prefix or suffix is connected; indeed the diameter is O(n). As a consequence, there is an O(n) interval broadcast algorithm. Prefixes which have t(n-1)! vertices for some t are especially well-behaved. The topology of, embeddings in, and algorithms for these graphs are considered, making use of the enumeration.>

For each value of the parameters $A,n,d$, a linear program exists whose integer solutions correspond to codes. The Plotkin bound gives a necessary and sufficient condition on $n/d$ for feasibility. Some further simple remarks on the tableau of the linear program can be made; it can also be modified to consider only linear codes. For A divisible by 4, codes with optimum $n/d$ with smallest possible value for n are Hadamard matrices. The question of a bound on n is an instance of the more general question of an upper bound on b for a block design with given v and k, which is conjectured to be polynomial in v. Some constructions related to these questions are given.

Previous article Full AccessErratum: An Interger Program for CodesMartin DowdMartin Dowdhttps://doi.org/10.1137/0404051PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Erratum: An Interger Program for Codes." SIAM Journal on Discrete Mathematics, 4(4), p. 589 Previous article FiguresRelatedReferencesCited byDetails Volume 4, Issue 4| 1991SIAM Journal on Discrete Mathematics History Submitted:14 May 1991Accepted:12 June 1991Published online:08 August 2006 InformationCopyright © 1991 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0404051Article page range:pp. 589-589ISSN (print):0895-4801ISSN (online):1095-7146Publisher:Society for Industrial and Applied Mathematics

A periodic sorting network consists of a sequence of identical blocks. In this paper, the periodic balanced sorting network, which consists of log n blocks, is introduced. Each block, called a balanced merging block, merges elements on the even input lines with those on the odd input lines. The periodic balanced sorting network sorts n items in O ([log n ] 2 ) time using ( n /2)(log n ) 2 comparators. Although these bounds are comparable to many existing sorting networks, the periodic structure enables a hardware implementation consisting of only one block with the output of the block recycled back as input until the output is sorted. An implementation of our network on the shuffle exchange interconnection model in which the direction of the comparators are all identical and fixed is also presented.

New relationships between questions in combinatorial number theory are shown. The Erdös-Turan conjecture is shown to be equivalent to the finite problem; the Erdös-Turan conjecture for N is shown to follow from that for Z; and the additive number theory of the integers and that of the finite bit strings under bitwise mod 2 addition are contrasted. The dual space technique from coding theory is applied to the integer question, leading to a lower bound on the number of collisions. A subsidiary question in coding theory is raised, which is a refinement of the perfect code theorem. Finally some computations for cyclic codes are given.

An Armstrong relation for a set of functional dependencies (FDs) is a relation that satisfies each FD implied by the set but no FD that is not implied by it.The structure and size (number of tuples) of Armstrong relatsons are investigated.Upper and lower bounds on the size of minimal-sized Armstrong relations are derived, and upper and lower bounds on the number of distinct entries that must appear m an Armstrong relation are given.It is shown that the time complexity of finding an Armstrong relation, gwen a set of functional dependencies, is precisely exponential in the number of attributes.Also shown ,s the falsity of a natural conjecture which says that almost all relations obeying a given set of FDs are Armstrong relations for that set of FDs.Finally, Armstrong relations are used to generahze a result, obtained by Demetrovics using quite complicated methods, about the possible sets of keys for a relauon.

This paper introduces a new sorting network, called the balanced sorting network, that sorts n items in O([lgn]2) time using (n/2)(lgn)2 comparators. Although these bounds are comparable to many existing sorting networks, the balanced sorting network possess some distinct advantages. In particular, its structure is highly regular consisting of a sequence of identicalbalanced merging networks. We prove that lg n identical merging networks are both necessary and sufficient to sort n items. We also present an explicit implementation of our network on the shuffle exchange interconnection model in which the direction of the comparitors are all identical and fixed.

@ is provable in certain arithmetic systems, then polynomial length proofs of the representing formulas exist in certain propositional systems. Two cases of this phenomenon and a general theory are given.