Trades, introduced by Hedayat [9], are two sets of blocks of elements which may be exchanged (traded) without altering the counts of certain subcollections of elements within their constituent blocks. They are of importance in applications where certain combinations of elements dynamically become prohibited from being placed in the same group of elements, since in this case one can trade the offending blocks with allowed ones. This is particularly the case in distributed storage systems, where due to privacy and other constraints, data of some groups of users cannot be stored together on the same server. We introduce a new class of balanced trades, important for access balancing of servers, and perturbation resilient balanced trades, important for studying the stability of server access frequencies with respect to changes in data popularity. The constructions and bounds on our new trade schemes rely on specialized selections of defining sets in minimal trades and number-theoretic analyses.

Abstract 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.

Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial \(S(t,t+1,v)\) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v , there is a Steiner triple system ( S (2, 3, v )) whose largest difference in block sums is within an additive constant of the lower bound.

We address the new problem of designing large families of subsets of a common labeled ground set that simultaneously have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the subsets is less than or equal to one. Our results include an upper bound on the size of such families, and constructions based on transversal designs, packings, and new forms of Latin rectangles. The constructions jointly optimize the size of the family of sets and the labeling scheme and achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The intersecting sets discrepancy problem is motivated by emerging applications in coding for molecular data storage.

We are concerned with the problem of designing large families of subsets over a common labeled ground set that have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the sets is less than or equal to one. Our results, based on transversal designs, factorizations of packings and Latin rectangles, show that by jointly constructing the sets and labeling scheme, one can achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The design problem considered is motivated by applications in molecular data storage.

A new algebraic system, test algebra (TA), is proposed for identifying faults in combinatorial testing for software-as-a-service (SaaS) applications. In the context of cloud computing, SaaS is a new software delivery model, in which mission-critical applications are composed, deployed, and executed on cloud platforms. Testing SaaS applications is challenging because new applications need to be tested once they are composed, and prior to their deployment. A composition of components providing services yields a configuration providing an SaaS application. While individual components in the configuration may have been thoroughly tested, faults still arise due to interactions among the components composed, making the configuration faulty. When there are k components, combinatorial testing algorithms can be used to identify faulty interactions with t or fewer components, for some threshold 2 ≤ t ≤ k on the size of interactions considered. In general, these methods do not identify specific faults, but rather indicate the presence or absence of some faults. To identify specific faults, an adaptive testing regime repeatedly constructs and tests configurations in order to determine, for each interaction of interest, whether it is faulty or not. In order to perform such testing in a loosely coupled distributed environment such as the cloud, it is imperative that testing results can be combined from many different servers. The TA defines rules to permit results to be combined, and to identify the faulty interactions. Using the TA, configurations can be tested concurrently on different servers and in any order. The TA always keeps the high reduction rate of potential faulty configurations in fault location analysis.

It has been conjectured that every Steiner triple system of order $v \neq 7$ has chromatic index at most $(v+3)/2$ when $v \equiv 3 {\:({\rm mod}\ 6)}$ and at most $(v+5)/2$ when $v \equiv 1 {\:({\rm mod}\ 6)}$. Herein, we construct a Steiner triple system of order $v$ with chromatic index at least $(v+3)/2$ for each integer $v \equiv 3 {\:({\rm mod}\ 6)}$ such that $v \geqslant 15$, with four possible exceptions. We further show that the maximum number of disjoint parallel classes in the systems constructed is sublinear in $v$. Finally, we establish for each order $v \equiv 15 {\:({\rm mod}\ 18)}$ that there are at least $v^{v^2(1/6+o(1))}$ nonisomorphic Steiner triple systems with chromatic index at least $(v+3)/2$ and that some of these systems are cyclic.

Covering arrays find important application in software and hardware interaction testing. For practical applications it is useful to determine or bound the minimum number of rows, $\mathsf{CAN}(t,k,v)$, in a covering array for given values of the parameters $t,k$, and $v$. Asymptotic upper bounds for $\mathsf{CAN}(t,k,v)$ have been established using the Stein--Lovász--Johnson strategy and the Lovász 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--Lovász--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 $\mathsf{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ász local lemma distribution.

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 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.

When $k$ factors each taking one of $v$ 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.

Software behavior depends on many factors. Combinatorial testing (CT) aims to generate small sets of test cases to uncover defects caused by those factors and their interactions. Covering array generation, a discrete optimization problem, is the most popular research area in the field of CT. Particle swarm optimization (PSO), an evolutionary search-based heuristic technique, has succeeded in generating covering arrays that are competitive in size. However, current PSO methods for covering array generation simply round the particle's position to an integer to handle the discrete search space. Moreover, no guidelines are available to effectively set PSOs parameters for this problem. In this paper, we extend the set-based PSO, an existing discrete PSO (DPSO) method, to covering array generation. Two auxiliary strategies (particle reinitialization and additional evaluation of gbest) are proposed to improve performance, and thus a novel DPSO for covering array generation is developed. Guidelines for parameter settings both for conventional PSO (CPSO) and for DPSO are developed systematically here. Discrete extensions of four existing PSO variants are developed, in order to further investigate the effectiveness of DPSO for covering array generation. Experiments show that CPSO can produce better results using the guidelines for parameter settings, and that DPSO can generate smaller covering arrays than CPSO and other existing evolutionary algorithms. DPSO is a promising improvement on PSO for covering array generation.

The largest strength of contention-based MAC protocols is simultaneously the largest weakness of their scheduled counterparts: the ability to adapt to changes in network conditions. For scheduling to be competitive in mobile wireless networks, continuous adaptation must be addressed. We propose ATLAS, an Adaptive Topology- and Load-Aware Scheduling protocol to address this problem. In ATLAS, each node employs a random schedule achieving its persistence, the fraction of time a node is permitted to transmit, that is computed in a topology and load dependent manner. A distributed auction (REACT) piggybacks offers and claims onto existing network traffic to compute a lexicographic max-min channel allocation. A node's persistence p is related to its allocation. Its schedule achieving p is updated where and when needed, without waiting for a frame boundary. We study how ATLAS adapts to controlled changes in topology and load. Our results show that ATLAS adapts to most network changes in less than 0.1s, with about 20 percent relative error, scaling with network size. We further study ATLAS in more dynamic networks showing that it keeps up with changes in topology and load sufficient for TCP to sustain multi-hop flows, a struggle in IEEE 802.11 networks. The stable performance of ATLAS supports the design of higher-layer services that inform, and are informed by, the underlying communication network.

SaaS (Software-as-a-Service) often uses multi-tenancy architecture (MTA) where tenant developers compose their applications online using the components stored in the SaaS database. Tenant applications need to be tested, and combinatorial testing can be used. While numerous combinatorial testing techniques are available, most of them produce static sequences of test configurations and their goal is often to provide sufficient coverage such as 2-way interaction coverage. But the goal of SaaS testing is to identify those compositions that are faulty for tenant applications. This paper proposes an adaptive test configuration generation algorithm AR (Adaptive Reasoning) that can rapidly identify those faulty combinations so that those faulty combinations cannot be selected by tenant developers for composition. The AR algorithm has been evaluated by both simulation and real experimentation using a MTA SaaS sample running on GAE (Google App Engine). Both the simulation and experiment showed show that the AR algorithm can identify those faulty combinations rapidly. Whenever a new component is submitted to the SaaS database, the AR algorithm can be applied so that any faulty interactions with new components can be identified to continue to support future tenant applications.

Breakthroughs in molecular profiling technologies are enabling a new data-intensive approach to biomedical research, with the potential to revolutionize how we study, manage, and treat complex diseases. The next great challenge for clinical applications of these innovations will be to create scalable computational solutions for intelligently linking complex biomedical patient data to clinically actionable knowledge. Traditional database management systems (DBMS) are not well suited to representing complex syntactic and semantic relationships in unstructured biomedical information, introducing barriers to realizing such solutions. We propose a scalable computational framework for addressing this need, which leverages a hypergraph-based data model and query language that may be better suited for representing complex multi-lateral, multi-scalar, and multi-dimensional relationships. We also discuss how this framework can be used to create rapid learning knowledge base systems to intelligently capture and relate complex patient data to biomedical knowledge in order to automate the recovery of clinically actionable information.

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 \in \{3,4,5\}$ to demonstrate the utility of the conditional expectation algorithm and the product construction.

The primary function of the medium access control (MAC) protocol is managing access to the shared communication channel. From the viewpoint of the transmitters, the MAC protocol determines each transmitter's channel occupancy, the fraction of time that it spends transmitting over the channel. In this paper, we define a set of topological persistences that conform to both network topology and traffic load. We employ these persistences as target occupancies for the MAC layer protocol. A centralized algorithm is developed for calculating topological persistences and its correctness is established. A distributed algorithm and implementation are developed that can operate within scheduled and contention-based MAC protocols. In the distributed algorithm, network resources are allocated through auctions at each receiver in which transmitters participate as bidders to converge on the topological allocation. Very low overhead is achieved by piggybacking auction and bidder communication on existing data packets. The practicality of the distributed algorithm is demonstrated in a wireless network via simulation using the ns-2 network simulator. Simulation results show fast convergence to the topological solution and, once operating with topological persistences, improved performance compared to IEEE 802.11 in delay, throughput, and drop rate.

Deterministic construction of measurement matrices for compressive sensing can be effected by first constructing a relatively small matrix explicitly, and then inflating it using a column replacement technique to form a large measurement matrix that supports at least the same level of sparsity. In particular, using easily developed null space conditions for l0- and l1-recoverability, properties of the pattern matrix used to select columns lead to well-studied matrices, separating and distributing hash families. Two-stage compression and recovery techniques are developed that employ more computationally intensive l0-recoverability for small matrices and simpler l1-recoverability for one larger matrix; this can reduce the number of measurements required.

Comparison of schedule and contention based MAC protocols is made difficult by their fundamental differences in approach to medium access control. This paper provides a way in which to analyze and compare MAC protocols regardless of their underlying allocation strategy. To that end a framework is developed in which the persistence of any protocol, contention- or schedule-based, can be measured. The framework is used to measure and compare the persistence levels of two prototypical contention- and schedule-based MACs, IEEE 802.11 and Scheduled p-Persistence. An ideal persistence that provides lexicographically max-min fair access to the channel is characterized, and used as a bandwidth allocation scheme. In addition to reducing the unfairness, simulations employing the ideal persistence values show increased throughput and decreased delay and drop rate when compared to either Scheduled p-Persistence or IEEE 802.11.

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'\in\{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 $K_n$ 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.

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 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 In a problem arising in grooming for two‐period optical networks, it is required to decompose the complete graph on n vertices into subgraphs each containing at most C edges, so that the induced subgraphs on a specified set of v ≤ n vertices each contain at most C ′ < C edges. The cost of the grooming is the sum, over all subgraphs, of the number of vertices of nonzero degree in the subgraph. The optimum grooming is the one of lowest cost. An integer linear programming formulation is used to determine precise lower bounds on this minimum cost for all choices of n and v when 1 ≤ C ′ < C ≤ 3. In most cases, this approach determines not only the bound but also the specific structure of any grooming that could realize the bound. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract Minimizing the number of add‐drop multiplexers (ADMs) in a unidirectional SONET ring can be formulated as a graph decomposition problem. When traffic requirements are uniform and all‐to‐all, groomings that minimize the number of ADMs (equivalently, the drop cost) have been characterized for grooming ratio at most six. However, when two different traffic requirements are supported, these solutions do not ensure optimality. In two‐period optical networks, n vertices are required to support a grooming ratio of C a in the first time period, while in the second time period a grooming ratio of C b , C b < C a , is required for v ≤ n vertices. This allows the two‐period grooming problem to be expressed as an optimization problem on graph decompositions of K n that embed graph decompositions of K v for v ≤ n . Using this formulation, optimal two‐period groomings are found for small grooming ratios using techniques from the theory of graphs and designs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

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 $\frac{1}{7}$ of the wavelength capacity, is determined within an additive constant. Indeed when the number n of sites satisfies $n \equiv 1$ (mod 3) and $n \neq 19$, the determination is exact; when $n \equiv 0$ (mod 3), $n \not\equiv 18$ (mod 24), and n is large enough, the determination is also exact; and when $n \equiv 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.

Algorithms for the construction of software interaction test suites have focussed on the special case of pairwise coverage; less is known about efficiently constructing test suites for higher strength coverage. The combinatorial growth of t-tuples associated with higher strength hinders the efficacy of interaction testing. Test suites are inherently large, so testers may not run entire test suites. To address these problems, we combine a simple greedy algorithmallwith heuristic search to construct and dispense one test at a time. Our algorithm attempts to maximize the number of t-tuples covered by the earliest tests so that if a tester only runs a partial test suite, they test as many t-tuples as possible.allHeuristic search is shown to provide effective methods for achieving such coverage.

We propose an improved online scheduler for multichannel or Wavelength Division Multiplexed (WDM) Ethernet Passive Optical Network (EPON) upstream transmission. This scheduler employs a just-in-time online scheduling framework to increase the number of Optical Network Units (ONUs) that can be scheduled concurrently. We outline the overall structure of this scheduling framework and discuss adapting offline scheduling policies for use in this framework. We compare the average queueing delay performance of different schedulers that follow this new framework to a simple online scheduler that schedules ONUs as soon as their REPORTS are received at the Optical Line Terminal (OLT). Further, we show how this framework can be used to provide differentiated service to ONUs without waiting for all ONUs to REPORT. We conclude with some remarks regarding our performance findings and possibilities for future research.

BACKGROUND: Multiple sequence alignment is fundamental. Exponential growth in computation time appears to be inevitable when an optimal alignment is required for many sequences. Exact costs of optimum alignments are therefore rarely computed. Consequently much effort has been invested in algorithms for alignment that are heuristic, or explore a restricted class of solutions. These give an upper bound on the alignment cost, but it is equally important to determine the quality of the solution obtained. In the absence of an optimal alignment with which to compare, lower bounds may be calculated to assess the quality of the alignment. As more effort is invested in improving upper bounds (alignment algorithms), it is therefore important to improve lower bounds as well. Although numerous cost metrics can be used to determine the quality of an alignment, many are based on sum-of-pairs (SP) measures and their generalizations. RESULTS: Two standard and two new methods are considered for using exact 2-way and 3-way alignments to compute lower bounds on total SP alignment cost; one new method fares well with respect to accuracy, while the other reduces the computation time. The first employs exhaustive computation of exact 3-way alignments, while the second employs an efficient heuristic to compute a much smaller number of exact 3-way alignments. Calculating all 3-way alignments exactly and computing their average improves lower bounds on sum of SP cost in v-way alignments. However judicious selection of a subset of all 3-way alignments can yield a further improvement with minimal additional effort. On the other hand, a simple heuristic to select a random subset of 3-way alignments (a random packing) yields accuracy comparable to averaging all 3-way alignments with substantially less computational effort. CONCLUSION: Calculation of lower bounds on SP cost (and thus the quality of an alignment) can be improved by employing a mixture of 3-way and 2-way alignments.

Abstract Network resilience measures the average two‐terminal reliability (connectedness) of a network. Multiterminal resilience extends this measure to any k vertices; it is the average k‐terminal reliability of a network. This generalizes two well‐studied network connectedness measures. Calculating multiterminal resilience on general networks encompasses all‐terminal reliability and thus is NP‐hard. Multiterminal resilience is examined on undirected series‐parallel networks, and an efficient (polynomial time) algorithm is developed for calculating the resilience for every k. Applications in mobile ad hoc and sensor networks are outlined. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 164–172 2007

Abstract 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.

Medium access control for multihop wireless sensor networks (WSNs) must be energy efficient because the battery-operated nodes are not practical to recharge. We give constructions for ternary schedules in which each node is in one of three states: transmitting, receiving, or asleep. For each hop (vi, vj), communication is effective only when viis transmitting, vjis receiving, and no other node in proximity of vjis also transmitting. Since sensor nodes are prone to failure, the schedules should be independent of the detailed topology while supporting spatial reuse. We use arc-decompositions of the complete lambda-fold directed graph Koarrninto directed complete bipartite subgraphs Koarra,bas a model for ternary scheduling in WSNs. We associate the vertices of Koarrnwith the nodes of the WSN, and occurrences of Koarra,bs (blocks) in the decomposition with time slots in the schedule. A block with out-vertices A and in-vertices B corresponds to a slot in which the a nodes in A are transmitting, the b in B are receiving, and all others are asleep. Such a decomposition of lambdaKoarrnguarantees that every ordered pair of nodes in the WSN can communicate in lambda time slots.

Off-chip buses account for a significant portion of the total system power consumed in embedded systems. Bus encoding schemes have been proposed to minimize power dissipation, but none has been demonstrated to be optimal with respect to any measure. In this paper, we give the first provably optimal and explicit (polynomial-time constructible) families of memoryless codes for minimizing bit transitions in off-chip buses. Our results imply that having access to a clock does not make a memoryless encoding scheme that minimizes bit transitions more powerful.

Greedy algorithms for the construction of software interaction test suites are studied. A framework is developed to evaluate a large class of greedy methods that build suites one test at a time. Within this framework are many instantiations of greedy methods generalizing those in the literature. Greedy algorithms are popular when the time for test suite construction is of paramount concern. We focus on the size of the test suite produced by each instantiation. Experiments are analyzed using statistical techniques to determine the importance of the implementation decisions within the framework. This framework provides a platform for optimizing the accuracy and speed of "one-test-at-a-time" greedy methods.

Combinatorial approaches to testing are used in several fields, and have recently gained momentum in the field of software testing through software interaction testing. One-test-at-a-time greedy algorithms are used to automatically construct such test suites. This paper discusses basic criteria of why greedy algorithms have been appropriate for this test gen-eration problem in the past and then expands upon how greedy algorithms can be utilized to address test suite pri-oritization.

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.

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.

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.

Summary form only given. Topology transparent scheduling for medium access control is an attractive technique for mobile ad hoc networks (MANETs) and sensor networks. The transmission schedule for each node is fixed and guarantees a bounded delay independent of which nodes are its neighbours, as long as the network is not too dense. Constructions of and performance criteria for topology transparent schedules have been extensively studied however, to date, frame synchronization is assumed. Synchronization is a difficult problem for MANETs and sensor networks. We study the relationships among topology transparent schedules, synchronization, and maximum delay. Frame synchronization, slot synchronization, and asynchronous transmission are the three synchronization models for this study. For each synchronization model, the first question is: (1) Do topology transparent schedules exist? If the answer to this question is yes, then two further questions are natural: (2) How to construct topology transparent schedules? (3) What is the least maximum delay? For frame and slot synchronization these three questions are answered in earlier work. We give answers for these three basic questions for asynchronous networks.

For sensor networks, throughput may not be the most important metric to optimize in medium access control. For many applications, periodic reports are desirable suggesting the need for a time division (TDMA) access scheme. However for many reasons, including nonuniformity of deployment and the large number of sensor nodes anticipated, TDMA is impractical. We explore scheduled persistence for medium access control in sensor networks. A continuum of approaches from simple randomized-persistent schedules at one extreme to topology-transparent schedules based on Steiner systems at the other are considered. We investigate the probability of obtaining a collision-free slot before a specified time (number of slots) and show that while the expected throughput of these approaches is the same, their variance is strikingly different. The schemes are also remarkably robust to high density. Furthermore, when schedules are chosen at random for each frame, scheduled persistence offers an interesting alternative for medium access control in sensor networks.

We formulate a combinatorial model of impulse radio sequences (IRSs) to study sequence or signal design for ultra-wideband (UWB) radio with unmodulated time 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).

We develop a connection between permutation arrays that are used in powerline communication and well-studied combinatorial objects, mutually orthogonal latin squares (MOLS). From this connection, many new results on permutation arrays can be obtained.

Complete interaction testing of components is too costly in all but the smallest systems. Yet component interactions are likely to cause unexpected faults. Recently, design of experiment techniques have been applied to software testing to guarantee a minimum coverage of all t-way interactions across components. However, t is always fixed. This paper examines the need to vary the size of t in an individual test suite and defines a new object, the variable strength covering array that has this property. We present some computational methods to find variable strength arrays and provide initial bounds for a group of these objects.

Software system faults are often caused by unexpected interactions among components. Yet the size of a test suite required to test all possible combinations of interactions can be prohibitive in even a moderately sized project. Instead, we may use pairwise or t-way testing to provide a guarantee that all pairs or t-way combinations of components are tested together This concept draws on methods used in statistical testing for manufacturing and has been extended to software system testing. A covering array, CA(N; t, k, v), is an N/spl times/k array on v symbols such that every N x t sub-array contains all ordered subsets from v symbols of size t at least once. The properties of these objects, however do not necessarily satisfy real software testing needs. Instead we examine a less studied object, the mixed level covering array and propose a new object, the variable strength covering array, which provides a more robust environment for software interaction testing. Initial results are presented suggesting that heuristic search techniques are more effective than some of the known greedy methods for finding smaller sized test suites. We present a discussion of an integrated approach for finding covering arrays and discuss how application of these techniques can be used to construct variable strength arrays.

Component based software development is prone to unexpected interaction faults. The goal is to test as many-potential interactions as is feasible within time and budget constraints. Two combinatorial objects, the orthogonal array and the covering array, can be used to generate test suites that provide a guarantee for coverage of all t-sets of component interactions in the case when the testing of all interactions is not possible. Methods for construction of these types of test suites have focused on two main areas. The first is finding new algebraic constructions that produce smaller test suites. The second is refining computational search algorithms to find smaller test suites more quickly. In this paper we explore one method for constructing covering arrays of strength three that combines algebraic constructions with computational search. This method leverages the computational efficiency and optimality of size obtained through algebraic constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide some new bounds for some strength three covering arrays.

MOTIVATION: 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. RESULTS: We describe a practical algorithm for the construction of optimal quality control designs that identify any faulty manufacturing step. The algorithm uses hillclimbing, a search technique from combinatorial optimization. We also present the results of using this algorithm on all practical quality control design sizes. AVAILABILITY: On request from the authors.

Dish arrays have been designed with two competing goals in mind, the ability to reconstruct erased disks (reliability), and the speed with which information can be read, written, and reconstructed (performance). The substantial loss in performance of write operations as reliability requirements increase has resulted in an emphasis on performance at the expense of reliability. This has proved acceptable given the relatively small members of disks in current disk arrays. We develop a method for improving the performance of write operations in disk arrays capable of correcting any double erasure, by ordering the columns of the erasure code to minimize the amount of parity information that requires updating. For large disk arrays, this affords a method to support the reliability needed without the generally accepted loss of performance.

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.

In the manufacture of oligo arrays for DNA hybridization experiments, manufacturing defects must be detected and their position determined. The design of manufacturing protocols for such oligo arrays leads to a combinatorial problem, requiring certain binary codes which have an additional balance property. Constructions using block designs and packings for these codes, within a range of interest in a practical manufacturing application, are developed. The focus is on equireplicate codes, constant weight codes in which every bit position is a one equally often.

Difference triangle sets are useful in many practical problems of information transmission. This article studies combinatorial and computational constructions for difference triangle sets having small scopes. Our algorithms have been used to produce difference triangle sets whose scopes are the best currently known.

For any simplicial complex $\Delta $ and field K, one can associate a graded K-algebra $K[\Delta ]$ (the Stanley–Reisner ring). For certain $\Delta $ and K, the Stanley–Reisner rings have a homogeneous system of parameters, $\Theta $, such that $K[\Delta ]/\langle \Theta \rangle $ is finite-dimensional, and coefficients of its Hilbert series are the h-vector of $\Delta $. The previous constructions of $\Theta $ were noncombinatorial. In the special case of cographic matroids, we give (for any field K) a combinatorial description of a homogeneous system of parameters in terms of the graph structure, as well as an explicit basis for the resulting quotient algebra. The results have applications to a central problem of reliability, namely the association of a multicomplex to a connected graph, such that the reliability is a simple function of the rank numbers.

Abstract Shanthikumar developed an upper bound for two‐terminal reliability based on consecutives – tcutsets. Subsequently, Shier generalized this strategy to obtain upper bounds from cutsets, and lower bounds from pathsets, when the cutsets or pathsets form a semilattice structure. We examine a restricted case of Shier's method that yields ak‐terminal lower bound based on consecutive pathsets. Our approach employs a common reduction of consecutive cut and path bounds to the computation of the two‐terminal reliability of an interval graph with imperfect vertices. Computational results are given to support the observation that the consecutive paths lower bound is competitive with the best efficiently computable bounds that are currently available. We then apply the consecutive path bound to reduce, in some cases dramatically, the number of states generated in a most probable state bounding method.

Abstract Three transformations on networks that reduce the all‐terminal network reliability (probability of connectedness) of a network are shown not to increase any coefficient in one form of the reliability polynomial of the network. These transformations yield efficiently computable lower bounds on each coefficient of the reliability polynomial. A further transformation due to Lomonosov is shown not to decrease any coefficient in the reliability polynomial, leading to an efficiently computable upper bound on each coefficient. The resulting bounds on coefficients can, in turn, be used to obtain a substantial improvement on the Ball—Provan strategy for computing lower and upper bounds on the all‐terminal reliability. © 1993 John Wiley & Sons, Inc.

Abstract An exact algebraic method for computing the two‐terminal reliabilities in a network is approximated to yield an effective upper bound that can be computed in time that is polynomial in the size of the network. The result yields both a strong aprioribound and a strong a posteriori technique for improving upper bounds from other upper‐bounding methods. ©1993 by John Wiley & Sons, Inc.

Efficient methods for determining the lower and upper bounds on the probabilities of source-to-terminal communication in a multistage interconnection network are developed. A novel lower bounding strategy (shifting) and a novel upper bounding strategy (renormalization) are presented; both can be computed in polynomial time. These strategies can be combined with existing methods based on coherence, and on consecutive cuts, to obtain an improvement on previously known efficiently computable bounds. A second efficient upper bound (averaging) is developed. An empirical evaluation of the bounds is discussed. Finally, the value of these bounding strategies in assessing the reliability of interconnection networks is examined.>

A channel graph is a directed acyclic graph with a unique source vertex and a unique sink vertex, in which all edges are partitioned into stages according to their distance from the source. The blocking probability of a channel graph is the probability that every source to sink path is blocked. A general transformation that never decreases the blocking probability is developed. This transformation leads to a short proof of a generalization of a theorem of K. Takagi (1971) and a theorem of F. R. K. Chung and F. K. Hwang (1978) in the case of the binomial model.>

Abstract In this paper, we show that every 3‐connected (3‐edge‐connected) planar graph contains a 2‐connected (respectively, 2‐edge‐connected) spanning partial 2‐tree (series‐parallel) graph. In contrast, a recent result implies that not all 3‐connected graphs contain 2‐edge‐connected series‐parallel spanning subgraphs.

The reliability of a graph G is the probability that G is connected, given that edges are independently operational with probability p. This is known to be a polynomial in p, and the location of the roots of these functions is discussed. In particular, it is conjectured that the roots of the reliability polynomial of any connected graph lie in the disc $| z - 1 | \leq 1$, and evidence for this conjecture is provided. It is shown that all real roots lie in $\{ 0 \} \cup ( 1,2 ]$ and that every graph has a subdivision for which the roots of the reliability polynomial lie in the conjectured disc.

Abstract A stochastic network in which nodes fail randomly with known probabilities is modeled by a probabilistic graph with unreliable nodes and perfect edges. The K ‐terminal reliability of such a network is the probability that there exists a Steiner tree connecting a subset of the nodes K (target nodes). Although the K ‐terminal reliability problem has been widely studied for networks with unreliable links, very little is known about the problem for networks with unreliable nodes. We show that computing this measure is computationally difficult, in particular #P‐complete. We then present efficient algorithms for the K ‐terminal reliability problem on two classes of perfect graphs; interval graphs and permutation graphs. Computing the reliability on these two classes of graphs is of particular interest since the problem remains #P‐complete for larger classes in the hierarchy of perfect graphs, namely, comparability and chordal graphs. The model presented in this paper is appropriate for radio broadcast networks and for fault‐tolerant multiprocessor networks.

Abstract A simplified model of a communications network is a probabilistic graph in which each edge operates with the same probability. The all‐terminal reliability , or probability that all nodes are connected, can be expressed as a polynomial in the edge operation probability. The coefficients of this polynomial are obtained from an interval partitioning of the cographic matroid, and only the first few coefficients can be computed efficiently. One of the best sets of efficiently computable reliability bounds is the Ball‐Provan bounds. These bounds are obtained using the efficiently computable coefficients and can be improved substantially if additional coefficients are known. In this paper, we develop a Monte Carlo method for estimating additional coefficients by randomly sampling over spanning trees of the network. Confidence intervals for all‐terminal reliability are obtained by using these estimates as additional constraints in the Ball‐Provan bounds. This approach has some advantages over conventional Monte Carlo point estimate methods. In particular, the computational complexity does not depend on the reliability of the network.

The two-terminal reliability problem for communication networks with unreliable links is a computationally difficult problem. Upper and lower bounds can be efficiently computed using graph-theoretical techniques based on edge-packing. We present a new technique for improving these bounds via approximation by series-parallel graphs. We also present some computational results for comparison with the known edge-packing bounds. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract Multiplictive inequalities for reliability bounds are derived, by observing that certain reliability measures are positively correlated. These inequalities can be used to obtain substantial improvements on available bounds for network reliability.

Abstract Many bounds for the all‐terminal reliability of computer networks have been proposed. Of those computable in polynomial time, the Ball‐Provan bounds and the Lomonosov Polesskii bounds provide the tightest estimates. A strategy is developed here using linear programming to obtain bounds which are tighter than both the Lomonosov‐Polesskii and the Ball‐Provan bounds. Computational results on these new bounds are also reported.

In order to relate the chromatic and all-terminal reliability polynomials, a simple two-variable polynomial is introduced. The latter polynomial is defined on a set system; as a result, many similarities between the chromatic and all-terminal reliability polynomials can be derived. In fact, within this general framework it is often possible to generalize from one of these two graph polynomials in order to get new results for the other.

Abstract The probability that a computer network is operational in an environment of statistically independent link failures has been widely studied. Three natural problems arise, when all nodes are to be connected (all‐terminal reliability), when two nodes are to communicate (2‐terminal reliability), and when k specified nodes are to communicate (k‐terminal reliability); the latter case includes the first two. Each of these reliability measures is NP‐hard to compute, and thus efficiently computable reliability bounds are of significant interest. To date, the all‐terminal and 2‐terminal cases have been treated separately, and few results apply to the k‐terminal case. In this paper, we develop a simple strategy to obtain k‐terminal reliability bounds. In the process, we demonstrate improvements on the previous best bounds for all‐terminal, k‐terminal, and 2‐terminal reliability. Computational experience with these new bounds is reported, by comparing the new lower bounds to existing lower bounds.

Abstract The design of reliable communications networks is an interesting and important topic. Perhaps the most common measure of reliability is a probabilistic one: the probability that a network is connected given the possibility of statistically independent line failures. In general, this is not efficiently computable. In this article, we develop a formula for the reliability of the most reliable maximal series‐parallel networks. The most reliable maximal series‐parallel networks are those maximal series‐parallel networks with the minimum number of vertices of degree 2, independent of many of the simpler reliability estimates. A two‐dimensional recurrence relating networks of varying sizes and edge deficiencies provides a generating function which in turn is exploited to give a simple closed expression for reliability.

The optimum communication spanning tree problem is to locate a spanning tree which minimizes the sum of the lengths of the shortest routes between all pairs of vertices in a graph, weighted by traffic requirements. Although NP-complete in general, this problem has an efficient solution for series-parallel graphs when all requirements are equal. This problem was introduced by Hu, who gave an efficient solution for the restricted case when the network is complete and the distances are equal.

The dynamic behavior of executing programs is a significant factor in the performance of virtual memory computer systems. Program restructuring attempts to improve the behavior of programs by reorganizing their object code to account for the characteristics of the virtual memory environment. A significant component of the restructuring process involves a restructuring graph. An analysis of restructuring graphs of typical programs found edge weights to be distributed in a Bradford–Zipf fashion, implying that a large fraction of total edge weight is concentrated in relatively few edges. This empirical observation can be used to improve the clustering phase of program restructuring, by limiting consideration to edges of large weight. We consider the effect of this improved clustering in the restructuring process by examining various means of restructuring some typical programs. In our experiments, 95 percent of the total edge value is typically accounted for by 50–60 percent of the edges. For naive clustering algorithms, clustering time is therefore typically halved; for more sophisticated methods, more substantial savings result. Finally, clustering with 95 percent of total edge value typically results in only a small decay in performance measures such as number of page faults and average working set size.

Abstract Minimum isolated failure immune networks are shown to be 2–trees. Further, subgraphs of 2‐trees are shown to be exactly those graphs which contain no subgraph homeomorphic to the four‐vertex complete graph. Together, these two characterizations yield a linear time algorithm for adding lines to a network to produce a minimum isolated failure immune network, whenever this is possible. This same algorithm, in conjunction with a linear time Steiner tree algorithm for 2‐tress, yields a linear time Steiner tree algorithm for partial 2‐tress. This contrasts with the known NP‐completeness of the Steiner tree problem for planar graphs.

A branch-and-bound algorithm for finding an optimal colouring of the blocks of a Steiner triple system is developed. Two simple but powerful heuristics are devised which improve the method. Applications to scheduling and the design of experiments are outlined.

Abstract A polynomial time algorithm for testing isomorphism of permutation graphs (comparability graphs of 2‐dimensional partial orders) is described. It operates by performing two types of simplifying transformations on the graph; the contraction of duplicate vertices and the contraction of uniquely orientable induced subgraphs.

An algorithm based upon Edmonds’s procedure for testing isomorphism of trees is extended to answer various questions concerning automorphisms of a labeled forest. This and linear pattern matching techniques are used to build efficient algorithms which find the automorphism partition and a set of generators for the automorphism group, determine the order of the automorphism group, and compute a coding for forests, interval graphs, outerplanar graphs, and planar graphs.