Search

Abstract: Group divisible covering designs (GDCDs) were introduced by Heinrich and Yin as a natural generalization of both covering designs and group divisible designs. They have applications in software testing and universal data compression. The minimum number of blocks in a k‐GDCD of type g u is a covering number denoted by C ( k , g u ). When k = 3, the values of C ( 3 , g u ) have been determined completely for all possible pairs ( g , u ). When k = 4, Francetić et al. constructed many families of optimal GDCDs, but the determination remained far from complete. In this paper, two specific 4‐IGDDs are constructed, thereby completing the existence problem for 4‐IGDDs of type ( g , h ) u. Then, additional families of optimal 4‐GDCDs are constructed. Consequently the cases for ( g , u ) whose status remains undetermined arise when g ≡ 7 mod 12 and u ≡ 3 mod 6, when g ≡ 11 , 14 , 17 , 23 mod 24 and u ≡ 5 mod 6, and in several small families for which one of g and u is fixed. [ABSTRACT FROM AUTHOR]

A covering array t-CA(n, k, g), of size n, strength t, degree k, and order g, is a k×n array on g symbols such that every t×n sub-array contains every t×1 column on g symbols at least once. Covering arrays have been studied for their applications to software testing, hardware testing, drug screening, and in areas where interactions of multiple parameters are to be tested. In this paper, we present an algebraic construction that improves many of the best known upper bounds on n for covering arrays 4-CA(n, k, 3). The t-coverage of a testing array A is the number of distinct t-tuples contained in the column vectors of A divided by the total number of t-tuples. If the testing array is a covering array of strength t, its t-coverage is 100%. The covering arrays with budget constraints problem is the problem of constructing a testing array of size at most n having largest possible coverage, given values of t, k, g and n. This paper also presents several testing arrays with high 4-coverage. [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]

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]

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]

For a prime power $${q \equiv 1 (mod{v})}$$ , the q × q cyclotomic matrix, whose entries are the discrete logarithms modulo v of the entries in the addition table of $${\mathbb{F}_q}$$ , has been shown using character theoretic arguments to produce an $${\varepsilon}$$ -biased array, provided that q is large enough as a function of v and $${\varepsilon}$$ . A suitable choice of $${\varepsilon}$$ ensures that the array is a covering array of strength t when $${q > t^2 v^{4t}}$$ . On the other hand, when v = 2, using a different character-theoretic argument the matrix has been shown to be a covering array of strength t when $${q > t^2 2^{2t-2}}$$ . The restrictions on $${\varepsilon}$$ -biased arrays are more severe than on covering arrays. This is exploited to prove that for all v ≥ 2, the matrix is a covering array of strength t whenever $${q > t^2 v^{2t}}$$ , again using character theory. A number of constructions of covering arrays arise by developing and extending the cyclotomic matrix. For each construction, extensive computations for various choices of t and v are reported that determine the precise set of small primes for which the construction produces a covering array. As a consequence, many covering arrays are found when q is smaller than the bound $${t^2 v^{2t}}$$ , and consequences for the existence of covering arrays reported. [ABSTRACT FROM AUTHOR]

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]

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]

Using cyclotomic numbers, a simple construction is presented for frequency-hopping (FH) sequences having optimal autocorrelation with respect to the well-known Lempel-Greenberger bound. Some optimal families of FH sequences are constructed. The simplicity of this technique makes it attractive for practical use. [ABSTRACT FROM AUTHOR]