Matching Items (5)
Description
Finding the optimal solution to a problem with an enormous search space can be challenging. Unless a combinatorial construction technique is found that also guarantees the optimality of the resulting solution, this could be an infeasible task. If such a technique is unavailable, different heuristic methods are generally used to improve the upper bound on the size of the optimal solution. This dissertation presents an alternative method which can be used to improve a solution to a problem rather than construct a solution from scratch. Necessity analysis, which is the key to this approach, is the process of analyzing the necessity of each element in a solution. The post-optimization algorithm presented here utilizes the result of the necessity analysis to improve the quality of the solution by eliminating unnecessary objects from the solution. While this technique could potentially be applied to different domains, this dissertation focuses on k-restriction problems, where a solution to the problem can be presented as an array. A scalable post-optimization algorithm for covering arrays is described, which starts from a valid solution and performs necessity analysis to iteratively improve the quality of the solution. It is shown that not only can this technique improve upon the previously best known results, it can also be added as a refinement step to any construction technique and in most cases further improvements are expected. The post-optimization algorithm is then modified to accommodate every k-restriction problem; and this generic algorithm can be used as a starting point to create a reasonable sized solution for any such problem. This generic algorithm is then further refined for hash family problems, by adding a conflict graph analysis to the necessity analysis phase. By recoloring the conflict graphs a new degree of flexibility is explored, which can further improve the quality of the solution.
ContributorsNayeri, Peyman (Author) / Colbourn, Charles (Thesis advisor) / Konjevod, Goran (Thesis advisor) / Sen, Arunabha (Committee member) / Stanzione Jr, Daniel (Committee member) / Arizona State University (Publisher)
Created2011
Description
Exhaustive testing is generally infeasible except in the smallest of systems. Research
has shown that testing the interactions among fewer (up to 6) components is generally
sufficient while retaining the capability to detect up to 99% of defects. This leads to a
substantial decrease in the number of tests. Covering arrays are combinatorial objects
that guarantee that every interaction is tested at least once.
In the absence of direct constructions, forming small covering arrays is generally
an expensive computational task. Algorithms to generate covering arrays have been
extensively studied yet no single algorithm provides the smallest solution. More
recently research has been directed towards a new technique called post-optimization.
These algorithms take an existing covering array and attempt to reduce its size.
This thesis presents a new idea for post-optimization by representing covering
arrays as graphs. Some properties of these graphs are established and the results are
contrasted with existing post-optimization algorithms. The idea is then generalized to
close variants of covering arrays with surprising results which in some cases reduce
the size by 30%. Applications of the method to generation and test prioritization are
studied and some interesting results are reported.
has shown that testing the interactions among fewer (up to 6) components is generally
sufficient while retaining the capability to detect up to 99% of defects. This leads to a
substantial decrease in the number of tests. Covering arrays are combinatorial objects
that guarantee that every interaction is tested at least once.
In the absence of direct constructions, forming small covering arrays is generally
an expensive computational task. Algorithms to generate covering arrays have been
extensively studied yet no single algorithm provides the smallest solution. More
recently research has been directed towards a new technique called post-optimization.
These algorithms take an existing covering array and attempt to reduce its size.
This thesis presents a new idea for post-optimization by representing covering
arrays as graphs. Some properties of these graphs are established and the results are
contrasted with existing post-optimization algorithms. The idea is then generalized to
close variants of covering arrays with surprising results which in some cases reduce
the size by 30%. Applications of the method to generation and test prioritization are
studied and some interesting results are reported.
ContributorsKaria, Rushang Vinod (Author) / Colbourn, Charles J (Thesis advisor) / Syrotiuk, Violet (Committee member) / Richa, Andréa W. (Committee member) / Arizona State University (Publisher)
Created2015
Description
In software testing, components are tested individually to make sure each performs as expected. The next step is to confirm that two or more components are able to work together. This stage of testing is often difficult because there can be numerous configurations between just two components.
Covering arrays are one way to ensure a set of tests will cover every possible configuration at least once. However, on systems with many settings, it is computationally intensive to run every possible test. Test prioritization methods can identify tests of greater importance. This concept of test prioritization can help determine which tests can be removed with minimal impact to the overall testing of the system.
This thesis presents three algorithms that generate covering arrays that test the interaction of every two components at least twice. These algorithms extend the functionality of an established greedy test prioritization method to ensure important components are selected in earlier tests. The algorithms are tested on various inputs and the results reveal that on average, the resulting covering arrays are two-fifths to one-half times smaller than a covering array generated through brute force.
Covering arrays are one way to ensure a set of tests will cover every possible configuration at least once. However, on systems with many settings, it is computationally intensive to run every possible test. Test prioritization methods can identify tests of greater importance. This concept of test prioritization can help determine which tests can be removed with minimal impact to the overall testing of the system.
This thesis presents three algorithms that generate covering arrays that test the interaction of every two components at least twice. These algorithms extend the functionality of an established greedy test prioritization method to ensure important components are selected in earlier tests. The algorithms are tested on various inputs and the results reveal that on average, the resulting covering arrays are two-fifths to one-half times smaller than a covering array generated through brute force.
ContributorsAng, Nicole (Author) / Syrotiuk, Violet (Thesis advisor) / Colbourn, Charles (Committee member) / Richa, Andrea (Committee member) / Arizona State University (Publisher)
Created2015
Description
Modern software and hardware systems are composed of a large number of components. Often different components of a system interact with each other in unforeseen and undesired ways to cause failures. Covering arrays are a useful mathematical tool for testing all possible t-way interactions among the components of a system.
The two major issues concerning covering arrays are explicit construction of a covering array, and exact or approximate determination of the covering array number---the minimum size of a covering array. Although these problems have been investigated extensively for the last couple of decades, in this thesis we present significant improvements on both of these questions using tools from the probabilistic method and randomized algorithms.
First, a series of improvements is developed on the previously known upper bounds on covering array numbers. An estimate for the discrete Stein-Lovász-Johnson bound is derived and the Stein- Lovász -Johnson bound is improved upon using an alteration strategy. Then group actions on the set of symbols are explored to establish two asymptotic upper bounds on covering array numbers that are tighter than any of the presently known bounds.
Second, an algorithmic paradigm, called the two-stage framework, is introduced for covering array construction. A number of concrete algorithms from this framework are analyzed, and it is shown that they outperform current methods in the range of parameter values that are of practical relevance. In some cases, a reduction in the number of tests by more than 50% is achieved.
Third, the Lovász local lemma is applied on covering perfect hash families to obtain an upper bound on covering array numbers that is tightest of all known bounds. This bound leads to a Moser-Tardos type algorithm that employs linear algebraic computation over finite fields to construct covering arrays. In some cases, this algorithm outperforms currently used methods by more than an 80% margin.
Finally, partial covering arrays are introduced to investigate a few practically relevant relaxations of the covering requirement. Using probabilistic methods, bounds are obtained on partial covering arrays that are significantly smaller than for covering arrays. Also, randomized algorithms are provided that construct such arrays in expected polynomial time.
The two major issues concerning covering arrays are explicit construction of a covering array, and exact or approximate determination of the covering array number---the minimum size of a covering array. Although these problems have been investigated extensively for the last couple of decades, in this thesis we present significant improvements on both of these questions using tools from the probabilistic method and randomized algorithms.
First, a series of improvements is developed on the previously known upper bounds on covering array numbers. An estimate for the discrete Stein-Lovász-Johnson bound is derived and the Stein- Lovász -Johnson bound is improved upon using an alteration strategy. Then group actions on the set of symbols are explored to establish two asymptotic upper bounds on covering array numbers that are tighter than any of the presently known bounds.
Second, an algorithmic paradigm, called the two-stage framework, is introduced for covering array construction. A number of concrete algorithms from this framework are analyzed, and it is shown that they outperform current methods in the range of parameter values that are of practical relevance. In some cases, a reduction in the number of tests by more than 50% is achieved.
Third, the Lovász local lemma is applied on covering perfect hash families to obtain an upper bound on covering array numbers that is tightest of all known bounds. This bound leads to a Moser-Tardos type algorithm that employs linear algebraic computation over finite fields to construct covering arrays. In some cases, this algorithm outperforms currently used methods by more than an 80% margin.
Finally, partial covering arrays are introduced to investigate a few practically relevant relaxations of the covering requirement. Using probabilistic methods, bounds are obtained on partial covering arrays that are significantly smaller than for covering arrays. Also, randomized algorithms are provided that construct such arrays in expected polynomial time.
ContributorsSarakāra, Kauśika (Author) / Colbourn, Charles J. (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Richa, Andréa W. (Committee member) / Syrotiuk, Violet R. (Committee member) / Arizona State University (Publisher)
Created2016
Description
Extremal graph theory results often provide minimum degree
conditions which guarantee a copy of one graph exists within
another. A perfect $F$-tiling of a graph $G$ is a collection
$\mathcal{F}$ of subgraphs of $G$ such that every element of
$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$
is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote
the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph
obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$
on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is
uniquely assigned to $e$. This dissertation proves for even
$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$
on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree
$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +
1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect
$C^{3}_{t}$-tiling. The result is tight, generalizing previous
results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,
let the minimum color degree $\delta^c(G)$ be the minimum number of
distinctly colored edges incident to a vertex. Call $G$ rainbow if
every edge has a unique color. For $\ell \geq 5$, this dissertation
proves that any sufficiently large edge colored graph $G$ on $n$
vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow
cycle on $\ell$ vertices. The result is tight for odd $\ell$ and
extends previous results for $\ell = 3$. In addition, for even
$\ell \geq 4$, this dissertation proves that any sufficiently large
edge colored graph $G$ on $n$ vertices with
$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where
$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$
vertices. The result is tight when $6 \nmid \ell$. As a related
result, this dissertation proves for all $\ell \geq 4$, that any
sufficiently large oriented graph $D$ on $n$ vertices with
$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on
$\ell$ vertices. This partially generalizes a result by Kelly,
K\uhn" and Osthus that uses minimum semidegree rather than minimum
out degree."
conditions which guarantee a copy of one graph exists within
another. A perfect $F$-tiling of a graph $G$ is a collection
$\mathcal{F}$ of subgraphs of $G$ such that every element of
$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$
is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote
the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph
obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$
on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is
uniquely assigned to $e$. This dissertation proves for even
$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$
on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree
$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +
1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect
$C^{3}_{t}$-tiling. The result is tight, generalizing previous
results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,
let the minimum color degree $\delta^c(G)$ be the minimum number of
distinctly colored edges incident to a vertex. Call $G$ rainbow if
every edge has a unique color. For $\ell \geq 5$, this dissertation
proves that any sufficiently large edge colored graph $G$ on $n$
vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow
cycle on $\ell$ vertices. The result is tight for odd $\ell$ and
extends previous results for $\ell = 3$. In addition, for even
$\ell \geq 4$, this dissertation proves that any sufficiently large
edge colored graph $G$ on $n$ vertices with
$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where
$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$
vertices. The result is tight when $6 \nmid \ell$. As a related
result, this dissertation proves for all $\ell \geq 4$, that any
sufficiently large oriented graph $D$ on $n$ vertices with
$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on
$\ell$ vertices. This partially generalizes a result by Kelly,
K\uhn" and Osthus that uses minimum semidegree rather than minimum
out degree."
ContributorsOursler, Roy (Author) / Arizona State University (Publisher)
Created2019