Search

By exploiting symmetries of finite fields, covering perfect hash families provide a succinct representation for covering arrays of index one. For certain parameters, this connection has led to both the best current asymptotic existence results and the best known efficient construction algorithms for covering arrays. The connection generalizes in a straightforward manner to arrays in which every t-way interaction is covered λ > 1 times, i.e., to covering arrays of index more than one. Using this framework, we focus on easily computed, explicit upper bounds on numbers of rows for various parameters with higher index. [ABSTRACT FROM AUTHOR]

Covering arrays are combinatorial objects that have been successfully applied in design of test suites for testing systems such as software, hardware, and networks where failures can be caused by the interaction between their parameters. Let n and k be positive integers with k ≥ 3. Two vectors x ∈ ℤ g 1 n and y ∈ ℤ g 2 n are qualitatively independent if for any ordered pair (a , b) ∈ ℤ g 1 × ℤ g 2 , there exists an index j ∈ { 0 , 1 , ... , n − 1 } such that (x (j) , y (j)) = (a , b). Let G be a graph with k vertices v 1 , v 2 , ... , v k with respective vertex weights g 1 , g 2 , ... , g k . A mixed covering array on G , denoted by CA (n , G , ∏ i = 1 k g i) , is a k × n array such that row i corresponds to vertex v i , entries in row i are from Z g i ; and if { v x , v y } is an edge in G , then the rows x , y are qualitatively independent. The parameter n is the size of the array. Given a weighted graph G , a mixed covering array on G with minimum size is optimal. In this paper, we introduce some basic graph operations to provide constructions for optimal mixed covering arrays on the family of graphs with treewidth at most three. [ABSTRACT FROM AUTHOR]

For a consecutive ordering of the edges of a graph G = (V , E) , the point sum of a vertex is the sum of the indices of edges incident with that vertex. Motivated by questions of balancing accesses in data placements in the presence of popularity rankings, an edge ordering is egalitarian when all point sums are equal, and almost egalitarian when two point sums differ by at most 1. It is established herein that complete graphs on n vertices admit an egalitarian edge ordering when n ≡ 1 , 2 , 3 (mod 4) and n ∉ { 3 , 5 } , or an almost egalitarian edge ordering when n ≡ 0 (mod 4) and n ≠ 4 . [ABSTRACT FROM AUTHOR]

The maximum independence number of Steiner triple systems of order v is well‐known. Motivated by questions of access balancing in storage systems, we determine the maximum total cardinality of a pair of disjoint independent sets of Steiner triple systems of order v for all admissible orders. [ABSTRACT FROM AUTHOR]

Column replacement techniques for creating covering arrays rely on the construction of perfect and distributing hash families with few rows, having as many columns as possible for a specified number of symbols. To construct distributing hash families in which the number of rows is less than the strength, we examine a method due to Blackburn and extend it in three ways. First, the method is generalized from homogeneous hash families (in which every row has the same number of symbols) to heterogeneous ones. Second, the extension treats distributing hash families, in which only separation into a prescribed number of parts is required, rather than perfect hash families, in which columns must be completely separated. Third, the requirements on one of the main ingredients are relaxed to permit the use of a large class of distributing hash families, which we call fractal. Constructions for fractal perfect and distributing hash families are given, and applications to the construction of perfect hash families of large strength are developed. [ABSTRACT FROM AUTHOR]

We construct orthogonal arrays OA λ (k , n) (of strength two) having a row that is repeated m times, where m is as large as possible. In particular, we consider OAs where the ratio m ∕ λ is as large as possible; these OAs are termed optimal. We provide constructions of optimal OAs for any k ≥ n + 1 , albeit with large λ. We also study basic OAs; these are optimal OAs in which gcd (m , λ) = 1. We construct a basic OA with n = 2 and k = 4 t + 1 , provided that a Hadamard matrix of order 8 t + 4 exists. This completely solves the problem of constructing basic OAs with n = 2 , modulo the Hadamard matrix conjecture. [ABSTRACT FROM AUTHOR]

Modern software systems often consist of many different components, each with a number of options. Although unit tests may reveal faulty options for individual components, functionally correct components may interact in unforeseen ways to cause a fault. Covering arrays are used to test for interactions among components systematically. A two‐stage framework, providing a number of concrete algorithms, is developed for the efficient construction of covering arrays. In the first stage, a time and memory efficient randomized algorithm covers most of the interactions. In the second stage, a more sophisticated search covers the remainder in relatively few tests. In this way, the storage limitations of the sophisticated search algorithms are avoided; hence, the range of the number of components for which the algorithm can be applied is extended, without increasing the number of tests. Many of the framework instantiations can be tuned to optimize a memory‐quality trade‐off, so that fewer tests can be achieved using more memory. [ABSTRACT FROM AUTHOR]

A classical construction of Bose produces a Steiner triple system of order 3 n from a symmetric, idempotent latin square of order n , which exists whenever n is odd. In an application to access-balancing in storage systems, certain Bose triple systems play a central role. A natural question arises: For which orders v does there exist a resolvable Bose triple system? Elementary counting establishes the necessary condition that v ≡ 9 (mod 18). For specific Bose triple systems that optimize an access metric, we show that v ≡ 9 (mod 18) is also sufficient. [ABSTRACT FROM AUTHOR]

A covering array CA(N;t, k, v) is an N × k array with entries in {1,2,…, v}, for which everyN × t subarray contains each t-tuple of {1,2,…, v}t among its rows. Covering arrays find application in interaction testing, including software and hardware testing, advanced materials development, and biological systems. A central question is to determine or bound CAN(t, k, v), the minimum number N of rows of a CA(N;t, k, v). The well known bound CAN(t, k, v) = O((t − 1)vt log k) is not too far from being asymptotically optimal. Sensible relaxations of the covering requirement arise when (1) the set {1,2,…, v}t need only be contained among the rows of at least(1−휖)kt of the N × t subarrays and (2) the rows of everyN × t subarray need only contain a (large) subset of {1,2,…, v}t. In this paper, using probabilistic methods, significant improvements on the covering array upper bound are established for both relaxations, and for the conjunction of the two. In each case, a randomized algorithm constructs such arrays in expected polynomial time. [ABSTRACT FROM AUTHOR]

A combinatorial framework for the construction of measurement matrices for compressive sensing is shown to exhibit great flexibility in signal recovery. The deterministic column replacement technique is hierarchical: Given as input a pattern matrix and ingredient measurement matrices, it produces a larger measurement matrix by replacing elements of the pattern matrix with columns from the ingredient matrices. Recovery for the measurement matrix produced does not rely on any fixed algorithm; rather it employs the recovery schemes of the ingredient matrices, which may differ from ingredient to ingredient. Because ingredient matrices can be much smaller than the measurement matrix produced, one can employ more computationally intensive recovery methods, sometimes resulting in fewer measurements. Noise can be accommodated in signal recovery by imposing additional conditions both on the pattern matrix and on the ingredient measurement matrices. [ABSTRACT FROM AUTHOR]

We use deterministic and probabilistic methods to analyze the performance of compressed sensing matrices constructed from Hadamard matrices and pairwise balanced designs, previously introduced by a subset of the authors. In this paper, we obtain upper and lower bounds on the sparsity of signals for which our matrices guarantee recovery. These bounds are tight to within a multiplicative factor of at most 4\sqrt 2 . We provide new theoretical results and detailed simulations, which indicate that the construction is competitive with Gaussian random matrices, and that recovery is tolerant to noise. A new recovery algorithm tailored to the construction is also given. [ABSTRACT FROM AUTHOR]

Covering arrays find important application in software and hardware interaction testing. For practical applications it is useful to determine or b ound the minimum number of rows, CAN(t, k, v), in a covering array for given values of the parameters t, k, and v. Asymptotic upper bounds for CAN(t, k, v) have been established using the Stein--Lovász--Johnson strategy and the Lovasz local lemma. A series of improvements on these bounds is developed in this paper. First an estimate for the discrete Stein--Lovász--Johnson bound is derived. Then using alteration, the Stein--Lovasz--Johnson bound is improved upon, leading to a two-stage construction algorithm. Bounds from the Lovász local lemma are improved upon in a different manner, by examining group actions on the set of symbols. Two asymptotic upper bounds on CAN(t, k, v) are established that are tighter than the known bounds. A two-stage bound is derived that employs the Lovász local lemma and the conditional Lováasz local lemma distribution. [ABSTRACT FROM AUTHOR]

When κ factors each taking one of ν levels may affect the correctness or performance of a complex system, a test is selected by setting each factor to one of its levels and determining whether the system functions as expected (passes the test) or not (fails). In our setting, each test failure can be attributed to at least one faulty (factor, level) pair. A nonadaptive test suite is a selection of such tests to be executed in parallel. One goal is to minimize the number of tests in a test suite from which we can determine which (factor, level) pairs are faulty, if any. In this paper, we determine the number of tests needed to locate faults when exactly one (or at most one) pair is faulty. To do this, we address an equivalent problem, to determine how many set partitions of a set of size N exist in which each partition contains v classes and no two classes in the partitions are equal. [ABSTRACT FROM AUTHOR]

Ordering the blocks of a design, the point sum of an element is the sum of the indices of blocks containing that element. Block labelling for popularity asks for the point sums to be as equal as possible. When all point sums are equal, the system is egalitarian; when point sums differ by at most one, it is almost egalitarian. For Steiner quadruple systems, a doubling construction is adapted to establish that an egalitarian S (3 , 4 , v) exists whenever v ≡ 4 , 20 (mod 24) and that an almost egalitarian S (3 , 4 , v) exists whenever v ≡ 8 , 16 (mod 24) and v ≠ 8. [ABSTRACT FROM AUTHOR]

Numerous constructions of the best known covering arrays are effective only for specific numbers of symbols. Fusion replaces numerous symbols by one, and can thereby employ such constructions to produce useful covering arrays on fewer symbols. Augmentation instead replaces one symbol by many, permitting the construction of covering arrays from those with fewer symbols. Until this time, augmentation has been of limited value because it introduces substantial redundant coverage. Here a general augmentation method is improved upon by analyzing the classes of interactions to be covered and employing variants of covering arrays, quilting arrays, to reduce the redundancy introduced. For strengths four, five, and six, quilting arrays are produced that can be used in the refined augmentation to produce many best known covering arrays. [ABSTRACT FROM AUTHOR]

• IPO strategy generates Covering Perfect Hash Families efficiently. • Fast covering array generation for large scale combinatorial testing. • Many improvements to upper bounds on CAN. • CPHFs with subspace restrictions lead to many different small CAs. Combinatorial testing makes it possible to test large systems effectively while maintaining certain coverage guarantees. At the same time, the construction of optimized covering arrays (CAs) with a large number of columns is a challenging task. Heuristic and Metaheuristic approaches often become inefficient when applied to large instances, as the computation of the quality for new moves or solutions during the search becomes too slow. Recently, the generation of covering perfect hash families (CPHFs) has led to vast improvements to the state of the art for many different instances of covering arrays. CPHFs can be considered a compact form of a specific family of covering arrays. Their compact representation makes it possible to apply heuristic methods for instances with a much larger number of columns. In this work, we adapt the ideas of the well-known In-Parameter-Order (IPO) strategy for covering array generation to efficiently construct CPHFs, and therefore implicitly covering arrays. We design a way to realize the concept of vertical extension steps in the context of CPHFs and discuss how a horizontal extension can be implemented in an efficient manner. Further, we develop a horizontal extension strategy for CPHFs with subspace restrictions that identifies candidate columns greedily based on conditional expectation. Then using a local optimization strategy, a candidate may be adjoined to the solution or may replace one of the existing columns. An extensive set of computational results yields many significant improvements on the sizes of the smallest known covering arrays. [ABSTRACT FROM AUTHOR]

Abstract: Necessary and sufficient conditions are established for an integer vector to be the -vector of some pure simplicial complex of rank three, and also for an integer vector to be the -vector of some pure simplicial multicomplex of rank three. For specified numbers of sets of cardinality one and cardinality two, an upper bound on the number of sets of cardinality three is established using shifting arguments. Then techniques from combinatorial design theory are used to establish a lower bound. Then it is shown that every number of sets of cardinality three between the lower and the upper bound can be realized. This characterization is restated to determine the precise spectrum of possible numbers of sets of cardinality two for specified numbers of sets of cardinality one and three. For simplicial complexes, these spectra are not always intervals, and the gaps are determined precisely. For simplicial multicomplexes, an alternative proof is given that these spectra are always intervals. [Copyright &y& Elsevier]

Sequential processes can encounter faults as a result of improper ordering of subsets of the events. In order to reveal faults caused by the relative ordering of t or fewer of v events, for some fixed t, a test suite must provide tests so that every ordering of every set of t or fewer events is exercised. Such a test suite is equivalent to a sequence covering array, a set of permutations on v events for which every subsequence of t or fewer events arises in at least one of the permutations. Equivalently it is a (different) set of permutations, a completely t-scrambling set of permutations, in which the images of every set of t chosen events include each of the t! possible "patterns." In event sequence testing, minimizing the number of permutations used is the principal objective. By developing a connection with covering arrays, lower bounds on this minimum in terms of the minimum number of rows in covering arrays are obtained. An existing bound on the largest v for which the minimum can equal t! is improved. A conditional expectation algorithm is developed to generate sequence covering arrays whose number of permutations never exceeds a specified logarithmic function of v when t is fixed, and this method is shown to operate in polynomial time. A recursive product construction is established when t = 3 to construct sequence covering arrays on vw events from ones on v and w events. Finally computational results are given for t ∈{3, 4, 5} to demonstrate the utility of the conditional expectation algorithm and the product construction. [ABSTRACT FROM AUTHOR]

Abstract: When a v-set can be equipped with a set of k-subsets so that every 2-subset of the v-set appears in exactly (or at most, or at least) one of the chosen k-subsets, the result is a balanced incomplete block design (or packing, or covering, respectively). For each k, balanced incomplete block designs are known to exist for all sufficiently large values of v that meet certain divisibility conditions. When these conditions are not met, one can ask for the packing with the most blocks and/or the covering with the fewest blocks. Elementary necessary conditions furnish an upper bound on the number of blocks in a packing and a lower bound on the number of blocks in a covering. In this paper it is shown that for all sufficiently large values of v, a packing and a covering on v elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on k. [Copyright &y& Elsevier]

Abstract: The construction of covering arrays with the fewest rows remains a challenging problem. Most computational and recursive constructions result in extensive repetition of coverage. While some is necessary, some is not. By reducing the repeated coverage, metaheuristic search techniques typically outperform simpler computational methods, but they have been applied in a limited set of cases. Time constraints often prevent them from finding an array of competitive size. We examine a different approach. Having used a simple computation or construction to find a covering array, we employ a post-optimization technique that repeatedly adjusts the array in an attempt to reduce its number of rows. At every stage the array retains full coverage. We demonstrate its value on a collection of previously best known arrays by eliminating, in some cases, 10% of their rows. In the well-studied case of strength two with twenty factors having ten values each, post-optimization produces a covering array with only 162 rows, improving on a wide variety of computational and combinatorial methods. We identify certain important features of covering arrays for which post-optimization is successful. [Copyright &y& Elsevier]

Abstract: A cover starter is a single vector that yields a covering array under the actions of groups on both the columns and the symbols of the starter. The existence of this compact representation of covering arrays facilitates effective exhaustive and heuristic search. When the group action on symbols fixes a small number of symbols, such cover starters lead to covering arrays that embed covering arrays on fewer symbols. Lower bounds on the length of cover starters over specified groups are established, and extensive computational results are developed to improve upper bounds for numerous covering array numbers. [Copyright &y& Elsevier]

Abstract: Grooming traffic in optical networks can be formulated as partitioning the edges of a graph into subgraphs each having at most a specified number of edges; a typical objective is to minimize the sum over all subgraphs of the vertices of nonzero degree (the drop cost). In practice, however, one may be constrained so that each vertex has nonzero degree in a limited number of different subgraphs of the partition. This is the load on the vertex, and the load of the grooming is the largest load at any vertex. The minimum load of a grooming for an -vertex -edge graph is determined here for all , , and . Indeed it is shown that in these cases drop cost and load can be minimized simultaneously. [Copyright &y& Elsevier]

Abstract: Covering arrays with mixed alphabet sizes, or mixed covering arrays, are useful generalizations of covering arrays that are motivated by software and network testing. Suppose that there are k factors, and that the ith factor takes values or levels from a set G i of size g i . A run is an assignment of an admissible level to each factor. A mixed covering array, MCA , is a collection of N runs such that for any t distinct factors, , every t-tuple from occurs in factors in at least one of the N runs. When , an MCA is a CA . The mixed covering array number, denoted by MCAN , is the minimum N for which an MCA exists. In this paper, we focus on the constructions of mixed covering arrays of strength three. The numbers MCAN are determined for all cases with and for most cases with . [Copyright &y& Elsevier]

Abstract: A Hanani triple system of order , , is a decomposition of the complete graph into sets of disjoint triangles and one set of disjoint triangles. A nearly Kirkman triple system of order , , is a decomposition of into sets of disjoint triangles; here is a one-factor of . The Hanani triple systems of order and the nearly Kirkman triple systems of order can be classified using the classification of the Steiner triple systems of order . This is carried out here for : There are 3787983639 isomorphism classes of s and 25328 isomorphism classes of s. Several properties of the classified systems are tabulated. In particular, seven of the s have orthogonal resolutions, and five of the s admit a pair of resolutions in which the almost parallel classes are orthogonal. [Copyright &y& Elsevier]

Abstract: Grooming uniform all-to-all traffic in optical ring networks with grooming ratio requires the determination of graph decompositions of the complete graph into subgraphs each having at most edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The minimum drop cost is determined for grooming ratio 9. Previously this bound was shown to be met when with two exceptions and eleven additional possible exceptions for , and also when with one exception and one possible exception for . In this paper it is shown that the bound is met for all with four exceptions for and one possible exception for . Using this result, it is further shown that when and is sufficiently large, the bound is also met. [Copyright &y& Elsevier]

Test response compaction for integrated circuits (ICs) with scan-based design-for-testability (DFT) support in the presence of unknown logic values (Xs) is investigated from a combinatorial viewpoint. The theoretical foundations of X-codes, employed in an X-tolerant compaction technique called X-compact, are examined. Through the formulation of a combinatorial model of X-compact, novel design techniques are developed for X-codes to detect a specified maximum number of errors in the presence of a specified maximum number of unknown logic values, while requiring only small fan-out. The special class of X-codes that results leads to an avoidance problem for configurations in combinatorial designs. General design methods and nonconstructive existence theorems to estimate the compaction ratio of an optimal X-compactor are also derived. [ABSTRACT FROM AUTHOR]

We study grooming for two-period optical networks, a variation of the traffic grooming problem for wavelength division multiplexed (WDM) ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time there is all-to-all uniform traffic among n nodes, each request using 1/C of the bandwidth; and during the second period there is all-to-all uniform traffic only among a subset V of v nodes, each request now being allowed to use 1/C' of the bandwidth, where C' < C. We determine the minimum drop cost (minimum number of add-drop multiplexers (ADMs)) for any n, v and C = 4 and C' ϵ (1, 2, 3). To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph Kn into subgraphs, where each subgraph has at most C edges and where furthermore it contains at most C' edges of the complete graph on v specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case. [ABSTRACT FROM AUTHOR]

A known recursive construction for perfect hash families multiplies the number of factors by q, where q is the largest prime power not exceeding the number of symbols. This is generalized to permit multiplication of the number of factors by powers of q; it is also improved upon by restricting the structure of the ingredient designs. For a perfect hash family of strength t, it may be possible to order its rows so that, for each , the first Ni rows form a perfect hash family of strength . This 'matroshka' ordering underlies a sometimes substantial reduction in the number of rows generated by the recursive construction. Perfect hash families with useful matroshka orderings are generated using linear orthogonal arrays, and with an effective one-row-at-a-time greedy algorithm. [ABSTRACT FROM AUTHOR]

Abstract: The existence of graph designs for the two nonisomorphic graphs on five vertices and eight edges is determined in the case of index one, with three possible exceptions in total. It is established that for the unique graph with vertex sequence (3, 3, 3, 3, 4), a graph design of order exists exactly when and , with the possible exception of . For the unique graph with vertex sequence , a graph design of order exists exactly when , with the possible exceptions of . [Copyright &y& Elsevier]

Abstract: Grooming uniform all-to-all traffic in optical ring networks with grooming ratio requires the determination of graph decompositions of the complete graph into subgraphs each having at most edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The minimum possible drop cost is determined for grooming ratio 8, and this cost is shown to be realized with six exceptions, and 37 possible exceptions, the largest being 105. [Copyright &y& Elsevier]

Abstract: Covering arrays have been extensively studied, in part because of their applications in testing interacting software components. In this setting, fast and flexible methods are needed to construct covering arrays of close-to-minimum size. However testing scenarios often impose additional structure on the tests that can be selected. We extend a greedy method to construct test suites for complex systems that have a hierarchical structure in which components combine to form subsystems, which in turn form larger subsystems, until the entire system is formed. The algorithm for merging covering arrays that we propose is then shown to have further potential application in the compression of multiple sequence alignments of genomic data. [Copyright &y& Elsevier]

Abstract: A -design of order embeds a given Steiner triple system if there is a subset of points on which the graphs of the design induce the blocks of the original Steiner triple system. It has been established that , and that when equality is met, such a minimum embedding of an STS() exists, except when . Equality only holds when . One natural question is: What is the smallest order such that some STS can be embedded into a -design of order ? We solve the problem for 7 of the 10 congruence classes modulo 30. [Copyright &y& Elsevier]

In order to reduce the number of add-drop multiplexers (ADMs) in SONET/WDM networks using wavelength add-drop multiplexing, certain graph decompositions can be used to form a "grooming" that specifies the assignment of traffic to wavelengths. When traffic among nodes is all-to-all and uniform, the drop cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The number of ADMs required is this drop cost. The existence of such decompositions with minimum cost, when every pair of sites employs no more than 1/7 of the wavelength capacity, is determined within an additive constant. Indeed when the number n of sites satisfies n ≡ 1 (mod 3) and n ≠ 19, the determination is exact; when n ≠ 0 (mod 3), n ≢ 18 (mod 24), and n is large enough, the determination is also exact; and when n ≠ 2 (mod 3) and n is large enough, the gap between the cost of the best construction and the cost of the lower bound is independent of n and does not exceed 4. [ABSTRACT FROM AUTHOR]

Abstract: A covering array is an array, in which in every subarray, each of the possible t-tuples over symbols occurs at least once. The parameter t is the strength of the array. Covering arrays have a wide range of applications for experimental screening designs, particularly for software interaction testing. A compact representation of certain covering arrays employs “permutation vectors” to encode subarrays of the covering array so that a covering perfect hash family whose entries correspond to permutation vectors yields a covering array. We introduce a method for effective search for covering arrays of this type using tabu search. Using this technique, improved covering arrays of strength 3, 4 and 5 have been found, as well as the first arrays of strength 6 and 7 found by computational search. [Copyright &y& Elsevier]

Abstract: A -design on points embeds a Steiner triple system (STS) if there is a subset of points on which the graphs of the design induce the blocks of a STS. It is established that , and that when equality is met that such a minimum embedding of an exists, except when . [Copyright &y& Elsevier]

Abstract: A graph is fully gated when every convex set of vertices is gated. Doignon posed the problem of characterizing fully gated graphs and in particular of deciding whether there is an efficient algorithm for their recognition. While the number of convex sets can be exponential, we establish that it suffices to examine only the convex hulls of pairs of vertices. This yields an elementary polynomial time algorithm for the recognition of fully gated graphs; however, it does not appear to lead to a simple structural characterization. In this direction, we establish that fully gated graphs are closed under a set of ‘convex’ operations, including a new operation which duplicates the vertices of a convex set (under some well-defined restrictions). This in turn establishes that every bipartite graph is an isometric subgraph of a fully gated graph, thereby severely limiting the potential for a characterization based on subgraphs. Finally, a large class of fully gated graphs is obtained using the presence of bipartite dominators, which suggests that simple convex operations cannot suffice to produce all fully gated graphs. [Copyright &y& Elsevier]

Abstract: A covering array is an array such that every sub-array contains all t-tuples from symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays. [Copyright &y& Elsevier]

Abstract: A covering array is an array such that every sub-array contains all t-tuples from symbols at least once, where t is the strength of the array. Covering arrays are used in experiments to screen for interactions among t-subsets of k components. Strength two covering arrays have been studied from numerous viewpoints, resulting in a variety of computational, direct, and recursive constructions. Consequently, it can be difficult to determine the smallest covering array that results from known construction. To address this, existence tables for the best currently known covering arrays are presented. In the process, a new direct construction from orthogonal arrays is also introduced. [Copyright &y& Elsevier]

Abstract: Edge-decompositions of the complete -fold directed graph into (uniform) directed complete bipartite subgraphs form a model for wireless communication in sensor networks. Each node can be in one of three states: asleep (powered down), listening, or transmitting. Communication requires that the sender be transmitting, the destination listening, and no other node near the receiver transmitting. We represent nodes of the network as the vertices of , and time slots for communication as blocks of the graph decomposition. A block with out-vertices A and in-vertices B corresponds to a slot in which the nodes in A are transmitting, those in B are receiving, and all others are asleep. Thus, such a decomposition of guarantees that every ordered pair of nodes in the associated network can communicate in time slots. Additional constraints are needed to minimize interference by a third node. Some recursive constructions for these graph decompositions are established, with particular emphasis on properties minimizing interference. [Copyright &y& Elsevier]

Abstract: A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword is the same for each codeword. These specialize to constant weight codes in the binary case, and permutation codes in the case that each symbol occurs exactly once. Constant composition codes arise in powerline communication and balanced scheduling, and are used in the construction of permutation codes. In this paper, direct and recursive methods are developed for the construction of constant composition codes. [Copyright &y& Elsevier]

SONET/WDM networks using wavelength add-drop multiplexing can be constructed using certain graph decompositions used to form a grooming, consisting of unions of primitive rings. The cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{6}$ of the wavelength capacity, is determined with a finite number of possible exceptions. Indeed, when the number N of sites satisfies $N \equiv 1 \pmod{3}$, the determination is complete, and when $N \equiv 2 \pmod{3}$, the only value left undetermined is N = 17. When $N \equiv 0 \pmod{3}$, a finite number of values of N remain, the largest being N = 2580. The techniques developed rely heavily on tools from combinatorial design theory. [ABSTRACT FROM AUTHOR]

Abstract: Let D be the triangle with an attached edge (i.e. D is the “kite”, a graph having vertices and edges , , , ). Bermond and Schönheim [G-decomposition of , where G has four vertices or less, Discrete Math. 19 (1977) 113–120] proved that a kite-design of order n exists if and only if . Let be a nontrivial kite-design of order , and let with . A path design of order and block size s is embedded into if there is an injective mapping such that B is an induced subgraph of for every . For each , we determine the spectrum of all integers such that there is a nontrivial path design of order and block size 3 embedded into a kite-design of order n. [Copyright &y& Elsevier]

Abstract: We prove that nets of order n with small deficiency d relative to n contain no hyperovals unless n is even and . Secondly, we examine the problems of the existence of r-nets of order with ovals or hyperovals; we are able to reduce these problems to a finite number of undetermined orders n. Thirdly, we prove the existence of a set of 7 incomplete mutually orthogonal Latin squares of order n with a hole of size 8 for every integer . As a corollary, there exists a 9-net of order n with a hyperoval for every . [Copyright &y& Elsevier]

A difference triangle set (D$\Delta$S) is a collection of sets of integers having the property that every integer can be written in at most one way as the difference of two elements within a set of the collection. The standard objective is to minimize the largest difference represented, given a specified size of the collection and sizes of the sets that it contains. In order to construct D$\Delta$Ss, we present a new type of combinatorial design, monotonic directed $(v,k,\lambda)$- designs (MDDs). Using MDDs, we give a general recursive construction for difference triangle sets (D$\Delta$Ss). Several instances of this main construction are derived. One of these, the perfect construction, leads to an infinite family of regular (optimal) D$\Delta$Ss if the existence of a single regular D$\Delta$S is known. [ABSTRACT FROM AUTHOR]

We formulate a combinatorial model of impulse radio sequences (IRSs) to study sequence or signal design for ultra-wideband (UWB) radio with unmodulated lime hopping. Using this combinatorial model for IRSs, we develop necessary and sufficient conditions for the existence of IRSs. Several novel constructions for IRSs with optimal correlation properties are given. The constructions involve the Welch construction for Costas arrays, a quadratic polynomial construction over finite fields, recursive techniques for optical orthogonal codes, and combinatorial design techniques using perfect Mendelsohn designs (PMDs). [ABSTRACT FROM AUTHOR]

In wavelength division multiplexing for unidirectional rings, traffic grooming is used to pack low rate signals into higher rate streams to share a wavelength. The grooming chosen determines the number of add-drop multiplexers used for the optical-to-electronic conversion. The determination of groomings to use the fewest multiplexers is equivalent to a graph design problem, which has been solved when up to four signals can be packed into a stream. We completely settle the case here when five signals pack into one stream, using old and new results on (K4-e)-designs. [Copyright &y& Elsevier]

In a systematic erasure code for the correction of two simultaneous erasures, each information symbol must have two associated parity symbols. When implemented in a redundant array of independent disks (RAID), performance requirements on the update penalty necessitate that each information symbol be associated with no more parity symbols than the two required. This leads to a simple graph model of the erasure codes, with parity symbols as vertices and information symbols as edges. Based on simulations of RAID performance, an ordering of the edges in which every sequence of three consecutive edges in the order induces as few vertices as possible is found to optimize access performance of the disk array. The ladder orderings to optimize performance are shown to exist for the complete graph Kn, except possibly when n∈{15,18,22}. [Copyright &y& Elsevier]

In this paper, we introduce an algorithmic scheme to find optimal (v,4,2)-OOCs of small orders. We determine the sizes of optimal (v,4,2)-OOCs up to v=44, with three possible exceptions. We also develop an algebraic method to generate all difference triples over Zv. [Copyright &y& Elsevier]

Steiner triple systems are well studied combinatorial designs that have been shown to possess properties desirable for the construction of multiple erasure codes in RAID architectures. The ordering of the columns in the parity check matrices of these codes affects system performance. Combinatorial problems involved in the generation of good and bad column orderings are defined, and examined for small numbers of accesses to consecutive data blocks in the disk array. [Copyright &y& Elsevier]

In a synchronous optical network ring, assignment of source-to-destination circuits to wavelengths must respect traffic requirements and minimize both the number of wavelengths and the amount of terminal conversion equipment. When traffic requirements are approximately equal on all source–destination circuits, the assignment can be modeled as a graph decomposition problem. In this setting, techniques from combinatorial design theory can be applied. These techniques are introduced in a simpler form when every source–destination circuit requires one quarter of a wavelength. More sophisticated design-theoretic methods are then developed to produce the required decompositions for all sufficiently large ring sizes, when each source–destination circuit requires one eighth of a wavelength. [Copyright &y& Elsevier]