Search

AbstractAlternative design and analysis methods for screening experiments based on locating arrays are presented. The number of runs in a locating array grows logarithmically based on the number of factors, providing efficient methods for screening complex engineered systems, especially those with large numbers of categorical factors having different numbers of levels. Our analysis method focuses on levels of factors in the identification of important main effects and two-way interactions. We demonstrate the validity of our design and analysis methods on both well-studied and synthetic data sets and investigate both statistical and combinatorial properties of locating arrays that appear to be related to their screening capability.

The effective construction of covering arrays for interaction testing relies on fast, practical algorithms. Such algorithms are needed to directly construct covering arrays and variants such as covering perfect hash families. However, they are also needed for a broader class of combinatorial arrays defined by combinatorial restrictions, such as perfect, separating, and distributing hash families. For moderate-to-large construction problems, greedy algorithms offer fast techniques that are general and flexible. Consequently they yield the best-known explicit construction for a wide variety of array parameters. Among the greedy algorithms, one-column-at-a-time methods (such as IPO) appear to provide the most efficient techniques. For some restrictions, however, one-row-at-a-time methods guarantee the construction of an array whose size matches that of a strong probabilistic bound. Despite the practical merits of the IPO-like algorithms, this accuracy guarantee has been lacking. In this paper, a framework for greedy algorithms for a broad class of combinatorial restrictions is developed. A one-selection-at-a-time algorithm chooses the entries of the array in arbitrary order while guaranteeing to meet the probabilistic bound. It is time-efficient and uses minimal storage, but entails substantial recomputation. By storing intermediate results, the method is specialized to obtain a general one-row-at-a-time method that is faster. Finally, it is specialized to a general one-column-at-a-time and to an IPO method that consume both less time and less storage than the one-row-at-a-time approach. Crucially, each method guarantees to meet the probabilistic bound for each of the combinatorial restrictions studied.

Two powerful recursive constructions of covering arrays of strengths three and four use difference covering arrays (DCAs). However, what is required in these constructions is not the algebraic structure of differences in a group, but rather that the DCAs produce covering arrays that are resolvable. Both constructions are strengthened by using resolvable covering arrays in place of DCAs. Many new difference covering arrays are found by computational methods, and resolvable covering arrays that do not arise from DCAs are produced. Improvements for bounds on covering array numbers are shown to be substantial.

Recursive constructions for covering arrays employ small ingredient covering arrays to build large ones. At present the most effective methods are ‘cut-and-paste’ (or Roux-type) and column replacement techniques. Both can introduce substantial duplication of coverage; if unnecessary duplication can be avoided, then the recursion can yield a smaller array. Two extensions of covering arrays are introduced here for that purpose. The first examines arrays that cover only certain of the t-way interactions; we call these quilting arrays. We develop constructions of such arrays, and generalize column replacement techniques to use them in the construction of covering arrays. The second examines some consequences of nesting covering arrays of smaller strength in those of larger strength; the intersections among the covering arrays so nested lead to improvements in Roux-type constructions. For both directions, we examine consequences for the existence of covering arrays.

Locating arrays are of interest in generating software test suites to cover all t-way component interactions and locate interaction faults in component-based systems. However, constructions of optimal locating arrays have not been studied systematically. Indeed, no useful lower bound has previously been determined, and only some sporadic examples of optimal locating arrays have been found. When a single fault is to be located, this article develops both a lower bound on the size of locating arrays and some methods of constructing optimal locating arrays. Some infinite series of optimal locating arrays are then obtained.

Network operation may require that a specified number kof nodes be able to communicate via paths consisting of operating edges and nodes. In an environment of node and edge failure, this leads to associated reliability measures. When the knodes are known in advance, this has been widely studied as k-terminal reliability; when the knodes are chosen uniformly at random, this has been studied as k-resilience. A third notion, when it suffices to have anyknodes communicate, is related to the expected size of the largest component in the network. We generalize these three measures to the probability that given hnodes chosen in advance and inodes chosen at random, they appear in a component of size at least k = h + i + j. As expected, for general networks, for most choices of (h, i, j) the computation is #P-complete and hence unlikely to admit a polynomial time algorithm. We develop polynomial time algorithms in the special case that the network is series-parallel, which subsume and generalize earlier methods for k-terminal reliability and k-resilience.

SYNOPTIC ABSTRACTD-optimal designs have proved useful in analyzing common factorial experiments involving multilevel categorical factors. When analyzed by ANOVA, they allow the estimation of coefficients in a regression equation and the contributions to the variance by the main effects and interactions. If the measurement of contribution to variance is necessary but the estimation of all interaction coefficients in the regression equation is not, it is possible to reduce the number of experimental runs below a minimum D-optimal design, using what we call truncated D-optimal screening designs. D-efficiency calculations are not available due to the singularity of the design matrix; another method must be used to pare down the matrix while maintaining reasonable estimation of the original full factorial data. Covering arrays are adapted to guide this reduction. Combining properties of D-optimal designs and covering arrays produces designs that perform well at estimating full factorial results. A method is then developed to target specific interactions prior to the design of the experiment when process specific knowledge is available to indicate which interactions are least important.

Service-oriented computing is a new software development paradigm that allows application builders to choose from many available services. The challenges are to efficiently determine which services are the most appropriate to combine into an application based on concerns such as functionalities, licensing costs, and known reliability. Group testing has addressed some issues on how to select a small subset of candidate services. We expand upon the group testing methodology with a greedy algorithm that generates biased covering arrays for interactive testing of the services selected by group testing.

A covering arrayCA(N;t,k,v) is an N × k array such that every N × t sub‐array contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006

A covering arrayCA(N;t,k, v is an N × k array such that every N × t subarray contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. The particular case when t = 2 (pairwise coverage) has been extensively studied, both to develop combinatorial constructions and to provide effective algorithmic search techniques. In this paper, a simple “cut‐and‐paste” construction is extended to covering arrays in which different columns (factors) admit different numbers of symbols (values); in the process an improved recursive construction for covering arrays with t = 2 is derived. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 124–138, 2006

Interaction testing is widely used in screening for faults. In software testing, it provides a natural mechanism for testing systems to be deployed on a variety of hardware and software configurations. Several algorithms published in the literature are used as tools to automatically generate these test suites; AETG is a well known example of a family of greedy algorithms that generate one test at a time. In many applications where interaction testing is needed, the entire test suite is not run as a result of time or cost constraints. In these situations, it is essential to prioritize the tests. Here we adapt a "one-test-at-a-time" greedy method to take importance of pairs into account. The method can be used to generate a set of tests in order, so that when run to completion all pairwise interactions are tested, but when terminated after any intermediate number of tests, those deemed most important are tested. Computational results on the method are reported.

A permutation array (or code) of length n and distance d is a set G of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x, y ? G is at least d. One motivation for coding with permutations is powerline communication. After summarizing known results, it is shown here that certain families of polynomials over finite fields give rise to permutation arrays. Additionally, several new computational constructions are given, often making use of automorphism groups. Finally, a recursive construction for permutation arrays is presented, using and motivating the more general notion of codes with constant weight composition.

We examine the combinatorial requirements of topology-transparent transmission schedules in a mobile ad hoc network (MANET). Specifically, if each of the N nodes has at most D active neighbors, we require the schedule to guarantee a collision-free transmission to each neighbor. This requirement is met by a cover-free family. We show that existing constructions for topology-transparent schedules correspond to an orthogonal array. Moreover, we show that Steiner systems support the largest number of nodes for a given schedule length. Both of these combinatorial objects are special cases of cover-free families. Analytically and numerically, we examine slot guarantees, expected throughput, and normalized expected throughput for systems of small strength, exploring the sensitivity of the response to D. Expected throughput provides a better performance metric than the minimum throughput results obtained earlier. The impact of a more realistic model of acknowledgments is also examined. The extension of the schedule to multiple frames returns us to the orthogonal arrays. The very density of Steiner systems that afforded an improvement over orthogonal arrays in one frame impedes the best extension to more frames.

In this paper, three new direct Mutually Orthogonal Latin Squares (MOLS) constructions are presented for 7 MOLS(24), 7 MOLS(75) and 8 MOLS(36); then using recursive methods, several new constructions for 7 and 8 MOLS are obtained. These reduce the largest value for which 7 MOLS are unknown from 780 to 570, and the largest odd value for which 8 MOLS are unknown from 1935 to 419. © 2003 Wiley Periodicals, Inc.

In [3], a general recursive construction for optical orthogonal codes is presented, that guarantees to approach the optimum asymptotically if the original families are asymptotically optimal. A challenging problem on OOCs is to obtain optimal OOCs, in particular with λ > 1. Recently we developed an algorithmic scheme based on the maximal clique problem (MCP) to search for optimal (n, 4, 2)‐OOCs for orders up to n = 44. In this paper, we concentrate on recursive constructions for optimal (n, 4, 2)‐OOCs. While “most” of the codewords can be constructed by general recursive techniques, there remains a gap in general between this and the optimal OOC. In some cases, this gap can be closed, giving recursive constructions for optimal (n, 4, 2)‐OOCs. This is predicated on reducing a series of recursive constructions for optimal (n, 4, 2)‐OOCs to a single, finite maximal clique problem. By solving these finite MCP problems, we can extend the general recursive construction for OOCs in [3] to obtain new recursive constructions that give an optimal (n · 2x, 4, 2)‐OOC with x ≥ 3, if there exists a CSQS(n). © 2004 Wiley Periodicals, Inc.

There are 50,024 Kirkman triple systems of order 21 admitting an automorphism of order 2. There are 13,280 Kirkman triple systems of order 21 admitting an automorphism of order 3. Together with the 192 known systems and some simple exchange operations, this leads to a collection of 63,745 nonisomorphic Kirkman triple systems of order 21. This includes \textit{all} KTS(21)s having a nontrivial automorphism group. None of these is doubly resolvable. Four are quadrilateral-free, providing the first examples of such a KTS(21).

Oligo arrays are important experimental tools for the high throughput measurement of gene expression levels. During production of oligo arrays, it is important to identify any faulty manufacturing step.

We study the hamiltonicity of certain graphs obtained from the hypercube as a means of producing a binary code of distance two and length n, whose codewords are ordered so that for each two consecutive codewords, one dominates the other. One vector dominates the other, if and only if, in all the positions where one of them has a zero, the other has a zero too. These dominated codes have applications in group testing for consecutive defectives. We also determine when the vectors can be ordered so that every two consecutive vectors have the domination property, and are at distance two; this is a natural generalization of Gray codes. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 294–302, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/jcd.10012

A quorum system is a set system in which any two subsets have nonempty intersection. Quorum systems have been extensively studied as a method of maintaining consistency in distributed systems. Important attributes of a quorum system include the load, balancing ratio, rank (i.e., quorum size), and availability. Many constructions have been presented in the literature for quorum systems in which these attributes take on optimal or otherwise favorable values. In this paper, we point out an elementary connection between quorum systems and the classical covering systems studied in combinatorial design theory. We look more closely at the quorum systems that are obtained from balanced incomplete block designs (BIBDs). We study the properties of these quorum systems and observe that they have load, balancing ratio, and rank that are all within a constant factor of being optimal. We also provide several observations about computing the failure polynomials of a quorum system (failure polynomials are used to measure availability). Asymptotic properties of failure polynomials have previously been analyzed for certain infinite families of quorum systems. We give an explicit formula for the failure polynomials for an easily constructed infinite class of quorum systems. We also develop two algorithms that are useful for computing failure polynomials for quorum systems and prove that computing failure polynomials is #P-hard. Computational results are presented for several “small” quorum systems obtained from BIBDs.

SONET/WDM networks using wavelength add—drop multiplexing can be constructed using certain graph decompositions used to form a “grooming,” consisting of unions of certain primitive rings. The existence of such decompositions when every pair of sites employs no more than ⅛ of the wavelength capacity is determined, with few possible exceptions, when the ring size is a multiple of four. The techniques developed rely heavily on tools from combinatorial design theory. © 2001 John Wiley & Sons, Inc.

Possible embeddings of transversal designs in the classical projective spaces on finite fields are characterized.

A graph is YΔY-reducible if it can be reduced to a vertex by a sequence of series-parallel reductions and YΔY-transformations. Terminals are distinguished vertices, that cannot be deleted by reductions and transformations. In this article, we show that four-terminal planar graphs are YΔY-reducible when at least three of the vertices lie on the same face. Using this result, we characterize YΔY-reducible projective-planar graphs. We also consider terminals in projective-planar graphs, and establish that graphs of crossing-number one are YΔY-reducible. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 83–93, 2000

A graph is YΔY‐reducibleif it can be reduced to a vertex by a sequence of series‐parallel reductions and YΔY‐transformations. Terminalsare distinguished vertices, that cannot be deleted by reductions and transformations. In this article, we show that four‐terminal planar graphs are YΔY‐reducible when at least three of the vertices lie on the same face. Using this result, we characterize YΔY‐reducible projective‐planar graphs. We also consider terminals in projective‐planar graphs, and establish that graphs of crossing‐number one are YΔY‐reducible. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 83–93, 2000

The existence of incomplete Steiner triple systems of order υ having holes of orders w and u meeting in z elements is examined, with emphasis on the disjoint (z = 0) and intersecting (z = 1) cases. When $w \ge u$ and $\upsilon=2w+u-2z$, the elementary necessary conditions are shown to be sufficient for all values of z. Then for $z\in\{0,1\}$ and υ “near” the minimum of $2w+u-2\,z$, the conditions are again shown to be sufficient. Consequences for larger orders are also discussed, in particular the proof that when one hole is at least three times as large as the other, the conditions are again sufficient. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 58–77, 2000

Doyen conjectured that there is no Steiner 2-design having an automorphism with more than r + 1 but fewer than $r + \sqrt{r - 1}$ fixed points, where r is the replication number. The falsity of this conjecture is shown by describing 2-(45, 5, 1) designs having an automorphism of order 2 with exactly 13 fixed points. © 1999 John Wiley & Sons, Inc. J Combin Design 7: 375–380, 1999

Constructions of balanced sampling plans excluding contiguous units, a class of designs introduced by Hedayat, Rao and Stufken, are given which provide a complete solution to this problem for block size three.

A subset of points in a transversal design is athwart if each block in the design has one of a small number of intersection sizes with the subset. Applications to the construction of mutually orthogonal latin squares are given. One particular case involves inequalities for the minimum number of distinct symbols appearing in an a×ß subarray of an×n latin square. Using thwarts, new transversal designs are determined for orders 408, 560, 600, 792, 856, 1046, 1059, 1368, 2164, 2328, 2424, 3288, 3448, 3960, 3992, 3994, 4025, 4056, 4824, 5496, 6264, 7768, 7800, 8096, and 9336.

The determination of the possible numbers of triples in a maximal partial triple system of order ? begun by Severn is completed. The result rests on the characterization of the maximum number of edges in a triangle-free, nonbipartite, antieulerian graph onn vertices.

A cyclic Steiner triple system, presented additively over Zv as a set B of starter blocks, has a non-trivial multiplier automorphism ? ? 1 when ?B is a set of starter blocks for the same Steiner triple system. When does a cyclic Steiner triple system of order v having a nontrivial multiplier automorphism exist? Constructions are developed for such systems; of most interest, a novel extension of Netto's classical construction for prime orders congruent to 1 (mod 6) to prime powers is proved. Nonexistence results are then established, particularly in the cases when v = (2ß + 1)a, when v = 9p with p = 5 (mod 6), and in certain cases when all prime divisors are congruent to 5 (mod 6). Finally, a complete solution is given for all v < 1000, in which the remaining cases are produced by simple computations.

Several new constructions for difference matrices are given. One class of constructions uses pairwise balanced designs to develop new difference matrices over the additive group of GF(q). A second class of constructions gives difference matrices over groups whose orders are not (necessarily) prime powers.

The number of states examined by most probable state algorithms for performability computations can be reduced dramatically by incorporating simple connectivity-based bounds, even when the performability measure is much more complex than connectivity. Modifications to Yang and Kubat's most probable state method are presented that permit the use of simple auxiliary bounds with only a small effect on the time per iteration. Computational results for a variety of performability measures are given.

In this article, we construct group divisible designs (GDDs) with block size five, group-type g^u and index unity. The necessary condition for the existence of such a GDD is u ≷ 5, (u - 1)g ≡ 0 (mod 4) and u(u - 1)g² ≡ 0 (mod 20). It is shown that these necessary conditions are also sufficient, except possibly in a few cases. Additionally, a new construction to obtain GDDs using holey TDs is presented. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 275–299, 1997

A complete arc in a design is a set of elements which contains no block and is maximal with respect to this property. The spectrum of sizes of complete arcs in Steiner triple systems is determined without exception here.

A generalization of a theorem of Lomonosov and Polesskii is proved, which provides a novel method for determining upper bounds on the probability that a graph contains a Steiner tree (k-terminal reliability).

Summary The existence of edge-coloured block designs with block size four is studied for all nonisomorphic colourings of the edges of aK4. There are 25 nonisomorphic edge-colouredK4's; for each, we examine the existence of edge-coloured designs with the minimum possible index. Uniform cases lead to block designs, perpendicular arrays, nested Steiner triple systems, idempotent Schroeder quasigroups, and other combinatorial objects.

Ac-hybrid triple system of orderv is a decomposition of the completev-vertex digraph intoc cyclic tournaments of order 3 and transitive tournaments of order 3. Hybrid triple systems generalize directed triple systems (c = 0) and Mendelsohn triple systems (c = v(v - 1)/3); omitting directions yields an underlying twofold triple system. The spectrum ofv andc for which ac-hybrid triple system of orderv exists is completely determined in this paper. Using (cubic) block intersection graphs, we then show that every twofold triple system of order underlies ac-hybrid triple system with . Examples are constructed for all sufficiently largev, for which this maximum is at most . The lower bound here is proved by establishing bounds onFi(n, r), the size of minimum cardinality vertex feedback sets inn-vertexi-connected cubic multigraphs havingr repeated edges. We establish that , 8$$ " />. These bounds are all tight, and the latter is used to derive the lower bound in the design theoretic problem.

Every graph having vertex degrees zero and two satisfying the basic necessary conditions is the leave of a maximal partial triple system, with one exception (C4 ?C5). The proof technique is direct, using the method of differences.

Using thwarts, new transversal designs are determined for orders 201, 336, 360, 365, 393, 429, 501, 749, 845, 1080, 1120, 1324, 1400, 1632, 1760, 1824, 1904, and for numerous larger orders. Incomplete transversal designs with block size 8, and PBDs having three consecutive block sizes, are also constructed from thwarts.

AbstractThe existence of 1-factorizations of the complete multigraph ?Knwhich cannot be decomposed into 1-factorizations with smaller ? is studied.

The resilience of a network is a measure of its reliability; it is the expected number of node pairs which can communicate. The resilience of an n-vertex series-parallel network can be computed in $O(n^2 )$ time. The algorithm employs the recursive structure of maximal series-parallel networks. In contrast to this, computing the resilience of a planar network is shown to be #P-complete.

New recursive and direct constructions for transversal designs of index more than one are established. Using these, the existence of transversal designs of index at least 2 and block size 8 is settled, with eight possible exceptions. Existence for block size 9 is settled with 44 possible exceptions.

This paper deals with existence results for pairwise balanced designs with block sizes 8, 9, and 10. Novel constructions using four level thwarts and Denniston arcs are developed.

A mitre in a Steiner triple system is a set of five triples on seven points, in which two are disjoint. Recursive constructions for Steiner triple systems containing no mitre are developed, leading to such anti-mitre systems for at least 9/16 of the admissible orders. Computational results for small cyclic Steiner triple systems are also included.

A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a more general weighted problem in precedence constrained scheduling.

Colbourn, Day, and Nel developed the first algorithm requiring at mostO(n3) arithmetic operations for ranking and unranking spanning trees of a graph (nis the number of vertices of the graph). We present two algorithms for the more general problem of ranking and unranking rooted spanning arborescences of a directed graph. The first is conceptually very simple and requiresO(n3) arithmetic operations. The second approach shows that the number of arithmetic operations can be reduced to the same as that of the best known algorithms for matrix multiplication.

The reliability of a network can be efficiently bounded using graph-theoretical techniques based on edge-packing. We examine the application of combinatorial theorems on edge-packing spanning trees, s, t-paths, and s, t-cuts to the determination of reliability bounds. The application of spanning trees has been studied by Polesskii, and the application of s, t-paths has been studied by Brecht and Colbourn. The use of edge-packings of s, t-cutsets has not been previously examined. We compare the resulting bounds with known bounds produced by different techniques, and establish that the edge-packing bounds often produce a substantial improvement. We also establish that three other edge-packing problems arising in reliability bounding are NP-complete, namely edge-packing by network cutsets, Steiner trees, and Steiner cutsets.

We prove that the number oft-wise balanced designs of ordern is asymptotically $$n\left( {(_t^n )/(t + 1)} \right)(1 + o(1))$$ , provided that blocks of sizet are permitted. In the process, we prove that the number oft-profiles (multisets of block sizes) is bounded below by $$\exp \left( {c_1 = \sqrt n \log n} \right)$$ and above by $$\exp \left( {c_2 = \sqrt n \log n} \right)$$ for constants c2>c1>0.

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersxandy. It is shown that for fixedxandythe problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersxandysatisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.

Equivalence of Hadamard matrices can be decided inO(log2n) space, and hence in subexponential time. These resource bounds follow from the existence of small distinguishing sets.

Coloring partial Steiner triple systems is shown to be NP-complete. Together with an embedding technique of Lindner, this provides a short proof of the NP-completeness of coloring block designs.