Search

A variety of probabilistic notions of network reliability of graphs and digraphs have been proposed and studied since the early 1950s. Although grounded in the engineering and logistics of network design and analysis, the research also spans pure and applied mathematics, with connections to areas as diverse as combinatorics and graph theory, combinatorial enumeration, optimization, probability theory, real and complex analysis, algebraic topology, commutative algebra, the design and analysis of algorithms, and computational complexity. In this paper we describe the landscape of various notions of network reliability, the roads well traveled, and some that appear likely to lead to meaningful and important journeys. [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]

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]

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 triple system is a collection of b blocks, each of size three, on a set of v points. It is j-balanced when every two j -sets of points appear in numbers of blocks that are as nearly equal as possible, and well balanced when it is j-balanced for each j ∈ {1, 2, 3}.Well-balanced systems arise in the minimization of variance in file availability in distributed file systems. It is shown that when a triple system that is 2-balanced and 3-balanced exists, so does one that is well balanced. Using known and new results on variants of group divisible designs, constructions for well-balanced triple systems are developed. Using these, the spectrum of pairs (v, b) for which such a well-balanced triple system exists is determined completely. [ABSTRACT FROM AUTHOR]

Necessary conditions for existence of a resolvable group divisible design (GDD) with block size 3 and type [ABSTRACT FROM AUTHOR]

Algorithmic construction of software interaction test suites has focussed on pairwise coverage; less is known about the efficient construction of test suites for t-way interactions with t≥3. This study extends an efficient density-based algorithm for pairwise coverage to generate t-way interaction test suites and shows that it guarantees a logarithmic upper bound on the size of the test suites as a function of the number of factors. To complement this theoretical guarantee, an implementation is outlined and some practical improvements are made. Computational comparisons with other published methods are reported. Many of the results improve upon those in the literature. However, limitations on the ability of one-test-at-a-time algorithms are also identified. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

There are many published algorithms for generating interaction test suites for software testing, exemplified by AETG, IPO, TCG, TConfig, simulated annealing and other heuristic search, and combinatorial design techniques. Among these, greedy one-test-at-a-time methods (such as AETG and TCG) have proven to be a reasonable compromise between the needs for small test suites, fast test-suite generation, and flexibility to accommodate a variety of testing scenarios. However, such methods suffer from the lack of a worst-case logarithmic guarantee on test suite size, while methods that provide such a guarantee at present are less efficient or flexible, or do not produce test suites that are competitive in size for practical testing scenarios. In this paper, a new algorithm establishes that efficient, greedy, one-test-at-a-time methods can indeed produce a logarithmic worst-case guarantee on the test suite size. In addition, this can be done while still producing test suites that are of competitive size, and in a time that is comparable to the published methods. It is deterministic, guaranteeing reproducibility. It generates only one candidate test at a time, permits users to ‘seed’ the test suite with specified tests, and allows users to specify constraints of combinations that should be avoided. Further, statistical analysis examines the impact of five variables used to tune this density algorithm for execution time and test suite size: weighting of density for factors, scaling of density, tie-breaking, use of multiple candidates, and multiple repetitions using randomization. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]