5,394 research outputs found
Preface
No full textIntroduction to the volume collecting the contributed papers presented at IWOCA 2019, the 30th International Workshop on Combinatorial Algorithms, held at the Dipartimento di Informatica, Università di Pisa, Italy, during July 23–25, 2019
Applications of Combinatorial Designs in Computer Science
No full textColbourn, Charles J.; van Oorschot, Paul C.. (1988). Applications of Combinatorial Designs in Computer Science. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/4799
The Spectrum of Support Sizes for Threefold Triple Systems
No full textColbourn, Charles J.; Mahmoodian, Ebadollah S.. (1987). The Spectrum of Support Sizes for Threefold Triple Systems. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/4750
Locating and Detecting Arrays for Interaction Faults
No full textThe identification of interaction faults in component-based systems has focused on indicating the presence of faults, rather than their location and magnitude. While this is a valuable step in screening a system for interaction faults prior to its release, it provides little information to assist in the correction of such faults. Consequently tests to reveal the location of interaction faults are of interest. The problem of nonadaptive location of interaction faults is formalized under the hypothesis that the system contains (at most) some number d of faults, each involving (at most) some number t of interacting factors. Restrictions on the number and size of the putative faults lead to numerous variants of the basic problem. The relationships between this class of problems and interaction testing using covering arrays to indicate the presence of faults, designed experiments to measure and model faults, and combinatorial group testing to locate faults in a more general testing scenario, are all examined. While each has some definite similarities with the fault location problems for component-based systems, each has some striking differences as well. In this paper, we formulate the combinatorial problems for locating and detecting arrays to undertake interaction fault location. Necessary conditions for existence are established, and using a close connection to covering arrays, asymptotic bounds on the size of minimal locating and detecting arrays are established.
A final version of this paper appears in J Comb Optim (2008) 15: 17-48
Partial Covering Arrays: Algorithms and Asymptotics
No full textA covering array CA(N;t, k, v) is an N × k array with entries in {1,2,..., v}, for which every N × t subarray contains each t-tuple of {1,2,..., v}^t among its rows. Covering arrays find application in interaction testing, including software and hardware testing, advanced materials development, and biological systems. A central question is to determine or bound CAN(t, k, v), the minimum number N of rows of a CA(N;t, k, v). The well known bound CAN(t, k, v) = O((t − 1)v^t) log k) is not too far from being asymptotically optimal. Sensible relaxations of the covering requirement arise when (1) the set {1,2,..., v}^t need only be contained among the rows of at least (1−)C(,) of the N × t subarrays and (2) the rows of every N × t subarray need only contain a (large) subset of {1,2,..., v}^t. In this paper, using probabilistic methods, significant improvements on the covering array upper bound are established for both relaxations, and for the conjunction of the two. In each case, a randomized algorithm constructs such arrays in expected polynomial time
Partial Covering Arrays: Algorithms and Asymptotics
No full textA covering array CA(N;t, k, v) is an N×k array with entries in {1,2,...,v}, for which every N×t subarray contain seach t-tuple of {1,2,...,v}^t among its rows. Covering arrays find application in interaction testing, including software and hardware testing, advanced materials development, and biological systems. A central question is to determine or bound CAN(t, k, v), the minimum number N of rows of a CA(N;t, k, v).The well known bound CAN(t, k, v)=O((t−1)v^t logk) is not too far from being asymptotically optimal. Sensible relaxations of the covering requirement arise when (1) the set{1,2,...,v}^t need only be contained among the rows of at least(1−ε)C(k,t) of the N×t subarrays and (2) the rows of every N×t subarray need only contain a (large)subset of{1,2,...,v}^t. In this paper, using probabilistic methods, significant improvements on the covering array upper bound are established for both relaxations, and for the conjunction of the two. In each case, a randomized algorithm constructs such arrays in expected polynomial time
Weakly Union-free Maximum Packings
No full text. Frankl and Furedi established that the largest number of 3-subsets of an n-set for which no four distinct sets A;B;C;D satisfy A [ B = C [ D is at most b n(n\Gamma1) 3 c. Chee, Colbourn, and Ling established that this upper bound is met, with few exceptions, when n j 0; 1 (mod 3). In this paper, it is established that the upper bound is also met with few exceptions when n j 2 (mod 3). Keywords: union-free hypergraph, twofold triple system, group testing 1. Introduction A group divisible design (GDD) is a triple (X; G; B) which satisfies the following properties: (1) G is a partition of a set X (of points) into subsets called groups, (2) B is a set of subsets of X (called blocks) such that a group and a block contain at most one common point, (3) every pair of points from distinct groups occurs in exactly blocks. The parameter is the index of the GDD, and jXj is its order. The grouptype (type) of the GDD is the multiset [jGj : G 2 G]. We usually use an "exponential" notation ..
A 2 h periodic variation in the low-mass X-ray binary Ser X-1
No full textSpectroscopy of the low-mass X-ray binary Ser X-1 using the Gran Telescopio Canarias have revealed a ?2 h periodic variability that is present in the three strongest emission lines. We tentatively interpret this variability as due to orbital motion, making it the first indication of the orbital period of Ser X-1. Together with the fact that the emission lines are remarkably narrow, but still resolved, we show that a main-sequence K dwarf together with a canonical 1.4 M? neutron star gives a good description of the system. In this scenario, the most likely place for the emission lines to arise is the accretion disc, instead of a localized region in the binary (such as the irradiated surface or the stream-impact point), and their narrowness is due instead to the low inclination (?10°) of Ser X-1
Letter from J. Charles Dennis, United States Attorney, to American Civil Liberties Union of Northern California, April 22, 1943
No full textLetter from J. Charles Dennis to the American Civil Liberties Union of Northern California, regarding the case United States of America vs. Gordon Kiyoshi Hirabayashi, docket no. 45738. Letter states: "Gentlemen: Receipt is acknowledged of your letter of April 21st, 1943 relative to the above entitled cause with the enclosed consent for filing of brief as amicus curiae for my signature. Supreme Court cases are conducted by the Solicitor General, Department of Justice, Washington, D.C. This office has no authority to consent. The original consent is enclosed."The ACLU-Northern California case file records contain legal documents and correspondence pertaining to the case Ex parte Mitsuye Endo (1944), in which the United States Supreme court unanimously ruled that the federal government could not indefinitely detain United States citizens who were loyal to the government. Files include documents related to the Gordon Hirabayashi Supreme Court case Hirabayashi v. United States
Edge-packing of graphs and network reliability
No full textAbstractThe 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
- …
