Drop cost and wavelength optimal two-period grooming with ratio 4 (2009)
Bermond, Jean-Claude, Colbourn, Charles J., Gionfriddo, Lucia, Quattrocchi, Gaetano, Valls, Ignasi Sau
We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming...
Michael P. Mcgarry, Martin Reisslein, Charles J. Colbourn, Martin Maier, Frank Aurzada, Michael Scheutzow
(WDM) EPONs. We take a scheduling theoretic approach to solving the grant scheduling problem. We introduce a two-layer structure of the scheduling problem and investigate techniques to be used at...
Locating and Detecting Arrays for Interaction Faults (2009)
Colbourn, Charles J., McClary, Daniel W.
The 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...
Drop cost and wavelength optimal two-period grooming with ratio 4 (2009)
Bermond, Jean-Claude, Colbourn, Charles J., Gionfriddo, Lucia, Quattrocchi, Gaetano, Sau Valls, Ignasi
We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming...
Drop cost and wavelength optimal two-period grooming with ratio 4 (2009)
Bermond, Jean-Claude, Colbourn, Charles J., Gionfriddo, Lucia, Quattrocchi, Gaetano, Sau Valls, Ignasi
We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming...
Charles J. Colbourn, Gaetano Quattrocchi
Let D be the triangle with an attached edge (i. e. D is the “kite”, a graph having
A Carrier Sense Multiple Access Protocol with (2008)
Power Backoff (csma/pb, Charles J. Colbourn, Minghao Cui, Violet R. Syrotiuk
Abstract — In this paper we propose an alternate approach to collision resolution in a CSMA protocol. Most contention protocols resolve collisions by backing off in time. We introduce spatial...
Just-in-Time Online Scheduling for WDM EPONs (2008)
Michael P. Mcgarry, Martin Reisslein, Charles J. Colbourn
Abstract — We propose an improved online scheduler for multichannel
Ehab S. Elmallah, Charles J. Colbourn
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 (seriesparallel) graph. In contrast, a...
Charles J. Colbourn, Ehab S. Elmallah
In the simple assignment problem, there are n processors, m tasks, and a relation between the processors and tasks; this relation indicates the ability of the processor to perform the task. When the...
Generating Sets in Steiner Triple Systems (2008)
Charles J. Colbourn, Jeffrey H. Dinitz
A k-generating set generalizes the notion of a complete arc. Consider the Steiner quasigroup (V; \Phi) of a Steiner triple system. Let W ae V . Then (some) elements of V nW can be written in the form...
Kirkman Triple Systems of Orders 21 and 27 (2007)
Myra B. Cohen, Charles J. Colbourn, Lee A. Ives
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...
An Application of Permutation Arrays to Block Ciphers (2007)
Douglas De La, Charles J. Colbourn
The maximum number of permutations with a specified maximum distance is considered in this paper. An application to a practical problem in the design of a 320-bit block cipher is given. 1...
NS1D0 Sequences and Anti-Pasch Steiner Triple Systems (2007)
Feliu Sagols, Charles J. Colbourn
We present an algorithmic construction of anti-Pasch Steiner triple systems for orders congruent to 9 mod 12. This is a Bose-type method derived from a particular type of 3-triangulations generated...
Transversal Designs in Classical Planes and Spaces (2007)
Aiden A. Bruen, Charles J. Colbourn
Possible embeddings of transversal designs in the classical projective spaces on finite fields are characterized. 1 Background A transversal design of order or group size n, block size k and index ,...
Steiner Triple Systems as Multiple Erasure Correcting Codes in Large Disk Arrays (2007)
Myra Cohen And, Myra B. Cohen, Charles J. Colbourn
Desirable RAID architectures provide fast performance with minimal overhead costs and short reconstruction times. As the number of disks in an array increases, however, the probability that...
Series-Parallel Subgraphs of Planar Graphs (2007)
Ehab S. Elmallah, Charles J. Colbourn
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...
(M,S)-Optimal Designs with Block Size Three (2007)
The existence of (M; S)-optimal designs for block size three is completely settled. Such a design is a collection of b triples on v elements so that for every two elements the numbers of triples...
On Uncollapsing Three Factor Orthogonal Main Effect Plans (2007)
Robert Gallant, Charles J. Colbourn
Math. Subject Classification 62K99, 05B15 Our main result is that any three-factor Orthogonal Main Effect Plan can be uncollapsed to obtain a tight three-factor Orthogonal Main Effect Plan. We also...
Pooling, Lattice Square, and Union Jack Designs (2007)
Mark A. Chateauneuf, Charles J. Colbourn, Donald L. Kreher, Esther R. Lamken, Esther R, David C. Torney
. Simplified pooling designs employ rows, columns, and principal diagonals from square and rectangular plates. The requirement that every two samples be tested together in exactly one pool leads to a...
Balanced Sampling Plans With Block Size Four Excluding Contiguous Units (2007)
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 when k = 4....
Laura P. Riccio, Charles J. Colbourn
We study the hamiltonicity of certain graphs obtained from the hypercube as a means to producing a binary code of distance two and length n, whose codewords are ordered so that for each two...
Kirkman Triple Systems of Orders 27, 33, and 39 (2007)
In the search for doubly resolvable Kirkman triple systems of order v, systems admitting an automorphism of order (v 3)=3 fixing three elements, and acting on the remaining elements in three orbits...
Ordering Disks for Double Erasure Codes (2007)
Affiliations Myra, B. Cohen, Myra B. Cohen, Charles J. Colbourn, Charles J. Colbourn, Charles J. Colbourn
Abstract: Disk 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...
Ian Stobert, Dan S. Archdeacon, Charles J. Colbourn, Sanjoy K. Baruah, Ph. D, Ph. D, ...
A surface is a compact, connected, Hausdorff space that is locally homeomorphic to IR 2. A spine is a topological-minimal embedding of a graph in a surface \Sigma with exactly one face which is an...
Jason Mimick, Dan S. Archdeacon, Sanjoy K. Baruah, Jeff H. Dinitz, Charles J. Colbourn, Ph. D, ...
A partially ordered set (poset) is a pair P = (X;!), where X is a set and! is a relation between pairs of elements from X. P is a partial order since some pairs of points may be incomparable. A...
A carrier sense multiple access protocol with power backoff (CSMA/PB) (2007)
Charles J. Colbourn, Minghao Cui, Errol L. Lloyd, Violet R. Syrotiuk
Prioritized Interaction Testing for Pairwise Coverage with Seeding and Contraints (2006)
Renee C. Bryce, Charles J. Colbourn
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...
Prioritized Interaction Testing for Pairwise Coverage with Seeding and Contraints (2006)
Renee C. Bryce, Charles J. Colbourn
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...
1 Lotto Designs 1.1 Definitions, Examples and Remarks (2006)
Charles J. Colbourn, Jeffrey H. Dinitz
1.1 Definition An (n, k, p, t)-lotto design is an n-set, V, of elements and a set B of kelement subsets (blocks) of V, so that for any p-subset P of V, there is a block B ∈ B, for which |P ∩ B |...
A Framework of Greedy Methods for Constructing Interaction Test Suites (2005)
Renee C. Bryce, Charles J. Colbourn, Myra B. Cohen
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....
Test Prioritization for Pairwise Interaction Coverage (2005)
Renee C. Bryce, Charles J. Colbourn
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...
Test Prioritization for Pairwise Interaction Coverage (2005)
Renee C. Bryce, Charles J. Colbourn
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...
A framework of greedy methods for constructing interaction test suites (2005)
Renée C. Bryce, Charles J. Colbourn
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....
Colbourn, C.: Ladder orderings of pairs and RAID performance (2004)
Myra B. Cohen, Charles J. Colbourn
Abstract. In a systematic erasure code for the correction of two simultaneous erasures, each information symbol must have two associated parity symbols. When implemented in a redundant array of...
A Deterministic Density Algorithm for Pairwise Interaction Coverage (2004)
Charles J. Colbourn, Myra B. Cohen
Pairwise coverage of factors affecting software has been proposed to screen for potential errors. Techniques to generate test suites for pairwise coverage are evaluated according to many criteria. A...
A deterministic density algorithm for pairwise interaction coverage (2004)
Pairwise coverage of factors affecting software has been proposed to screen for potential errors. Techniques to generate test suites for pairwise coverage are evaluated according to many criteria. A...
Constructing strength three covering arrays with augmented annealing. Discrete Mathematics (2003)
Myra B. Cohen, Charles J. Colbourn
A covering array CA(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. One application of these...
Steiner Triple Systems of Order 19 with Nontrivial Automorphism Group (2003)
Charles J. Colbourn, Spyros S. Magliveras, D.R. Stinson
There are 172,248 Steiner triple systems of order 19 having a nontrivial automorphism group. Computational methods suitable for generating these designs are developed.
Construction of optimal quality control for oligo arrays (2002)
Charles J. Colbourn, Martin Tompa
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...
Construction of optimal quality control for oligo arrays (2002)
Charles J. Colbourn, Martin Tompa
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...
Kirkman triple systems of order 21 with nontrivial automorphism group (2002)
Myra B. Cohen, Charles J. Colbourn, Lee A. Ives
Abstract. 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...
Construction of optimal quality control for oligo arrays (2002)
Colbourn, Charles J., Ling, Alan C. H., Tompa, Martin
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...
Equireplicate balanced binary codes for oligo arrays (2001)
Noga Alon, Beverley Sackler, Charles J. Colbourn, Martin Tompa
U.S.A. 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...
Minimum Weights of Point Codes of Steiner Triple Systems (2001)
The point code of a Steiner triple system always contains vectors of weight equal to the replication number. The existence of Steiner triple systems whose point code has minimum weight less than the...
Quorum systems constructed from combinatorial designs (2001)
Abstract 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...
Minimizing drop cost for SONET/WDM networks with 8 wavelength requirements (2001)
Charles J. Colbourn, Peng-jun Wan, Theory John Wiley
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...
Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs (2000)
Dan Archdeacon, Charles J. Colbourn, Isidoro Gitler, Centro De Investigaci'on, J. Scott Provan
A graph is Y \DeltaY-reducible if it can be reduced to a vertex by a sequence of series-parallel reductions and Y \DeltaY-transformations. Terminals are distinguished vertices which cannot be deleted...
Quorums from Difference Covers (2000)
Maekawa considered a simple but suboptimal grid-based quorum generation scheme in which N sites in the network are logically organized in the form of a p N \Theta p N grid, and the quorum sets are...
Asymptotically Optimal Erasure-Resilient Codes for Large Disk Arrays (2000)
Yeow Meng Chee, Charles J. Colbourn
Reliability is a major concern in the design of large disk arrays. Hellerstein et al. pioneered the study of erasure-resilient codes that allow one to reconstruct the original data even in the...
� c Springer-Verlag 1999 Pooling, Lattice Square, and Union Jack Designs (1999)
Mark A. Chateauneuf, Charles J. Colbourn, Donald L. Kreher, Esther R. Lamken, David C. Torney
Abstract. Simplified pooling designs employ rows, columns, and principal diagonals from square and rectangular plates. The requirement that every two samples be tested together in exactly one pool...
Wavelength Add-Drop Multiplexing For Minimizing Sonet Adms (1999)
Sonet Adms, Charles J. Colbourn, Charles J. Colbourn
In a SONET ring, assignment of source{to{destination circuits to wavelengths must respect trac requirements and minimize both the number of wavelengths and the amount of terminal conversion...
Bicoloring Steiner Triple Systems (1999)
Charles J. Colbourn, Jeffrey H. Dinitz, Alexander Rosa
A Steiner triple system has a bicoloring with m color classes if the points are partitioned into m subsets and the three points in every block are contained in exactly two of the color classes. In...
Minimizing Drop Cost for SONET/WDM Networks with 1/8 Wavelength Requirements (1999)
Charles J. Colbourn, Peng-jun Wan
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...
Mutually Orthogonal Latin Squares: A Brief Survey of Constructions (1999)
Charles J. Colbourn, Jeffrey H. Dinitz
In the two centuries since Euler first asked about mutually orthogonal latin squares, substantial progress has been made. The biggest breakthroughs came in 1960 with the celebrated theorems of Bose,...
Reliability Issues In Telecommunications Network Planning (1999)
Telecommunications network planning is concerned with the design and maintenance of large networks at reasonable cost, to deliver high capacity and speed. Loosely interpreted, "reliability"...
Orthogonal Arrays of Strength Three From Regular 3-Wise Balanced Designs (1999)
Charles J. Colbourn, D. L. Kreher, J. P. Mcsorley, D. R. Stinson
The construction given in [4] is extended to obtain new infinite families of orthogonal arrays of strength 3. Regular 3-wise balanced designs play a central role in this construction. 1 Introduction...
Group Testing for Consecutive Positives (1999)
. Strategies for adaptive and nonadaptive group testing are developed when the items are linearly ordered and the positive items form a consecutive subset of all items. Keywords: adaptive group...
Steiner Triple Systems with Disjoint or Intersecting Subsystems (1999)
Charles J. Colbourn, Monica A. Oravas, R. Rees
The existence of incomplete Steiner triple systems of order v 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....
Bicoloring Steiner Triple Systems (1999)
Charles J. Colbourn, Jeffrey H. Dinitz, Alexander Rosa
A Steiner triple system has a bicoloring with m color classes if the points are partitioned into m subsets and the three points in every block are contained in exactly two of the color classes. In...
Quorum Systems Constructed from Combinatorial Designs (1998)
Charles J. Colbourn, Jeffrey H. Dinitz, Douglas R. Stinson
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....
Covering Arrays of Strength Three (1998)
M. A. Chateauneuf, Charles J. Colbourn, D. L. Kreher
A covering array of size N , degree k, order v and strength t is a k \Theta N array with entries from a set of v symbols such that in any t \Theta N subarray every t \Theta 1 column occurs at least...
Four-Terminal Reducibility and Projective-Planar Wye-Delta-Wye-Reducible Graphs (1998)
Dan Archdeacon, Charles J. Colbourn, I. Gitler, Isidoro Gitler, Centro De Investigaci'on, J.S. Provan
A graph is Y \DeltaY -reducible if it can be reduced to a vertex by a sequence of series-parallel reductions and Y \DeltaY -transformations. Terminals are distinguished vertices which cannot be...
Reliability Polynomials: A Survey (1998)
Manoj Chari, Charles J. Colbourn
Computational and combinatorial problems concerning reliability polynomials are discussed. Recent results are surveyed, and some open problems mentioned. 1 The Basics A full treatment of the subject...
Sharper Bounds in Adaptive Group Testing (1998)
Laura Riccio, Charles J. Colbourn
Adaptive group testing in the presence of a large percentage of defectives is best done by individual testing rather than by pooling. The fraction of items which must be defective to make individual...
Weakly Union-free Maximum Packings (1998)
. 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...
Grade of Service Steiner Trees in Series-Parallel Networks (1998)
J. M. Smith, Charles J. Colbourn, Guoliang Xue
The grade of service Steiner tree problem is to determine the minimum total cost of an assignment of a grade of service to each link in a network, so that between each pair of nodes there is a path...
Modified Group Divisible Designs With Block Size Four (1998)
The existence of modified group divisible designs with block size four is settled with a handful of possible exceptions. 1 Introduction A group divisible design (GDD) is a triple (X; G; B) which...
Projective Planes and Congestion-Free Networks (1998)
The design of networks using broadcast media so that every two sites lie on a common link, subject to constraints on the number of links at each site (degree), and the number of sites on each link...
A Steiner 2-Design with an Automorphism Fixing Exactly r + 2 Points (1998)
Doyen conjectured that there is no Steiner 2-design having an automorphism with more than r + 1 but fewer than r + p r \Gamma 1 fixed points, where r is the replication number. The falsity of this...
Uniform Orthogonal Group Divisible Designs with Block Size Three (1996)
Charles J. Colbourn, Charles J. Colbourn, Peter B. Gibbons, Peter B. Gibbons
The spectrum of orthogonal group divisible designs with block size three, and u groups each of size g, is studied. Existence is settled with few possible exceptions for each group size g. 1...
Large Sets of Disjoint t-Designs (1996)
Yeow Meng Chee, Charles J. Colbourn, Donald L. Kreher
In this paper, we show how the basis reduction algorithm of Kreher and Radziszowski [4] can be used to construct large sets of disjoint designs with specified automorphisms. In particular, we...
Concerning the Generating Set of ... (1996)
The generating set of Z n is determined completely for n 8, with the exception of the (46,6,1) design. Some general results are presented for larger values of n. 1 Introduction A pairwise balanced...
More Thwarts in Transversal Designs (1996)
Charles Colbourn Combinatorics, Charles J. Colbourn, Jeffrey H. Dinitz, D. R. Stinson
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....
The CRC Handbook Of Combinatorial Designs (1995)
Charles J. Colbourn, Jeffrey H. Dinitz (Eds.), Jeffrey H. Dinitz, Leo Chouinard Ii, Robert Jajcay, S. S. Magliveras
Introduction A group (P; \Delta) is a set P , together with a binary operation \Delta on P , for which 1. an identity element e 2 P exists, i.e. x \Delta e = e \Delta x = e for all x 2 P ; 2. \Delta...
Some Open Problems on Reliability Polynomials (1993)
By Charles, Charles J. Colbourn
Some open questions, both computational and combinatorial, concerning reliability polynomials are discussed. 1 The Basics Our goal here is to state some tantalizing open problems concerning...
Some Open Problems on Reliability Polynomials (1993)
Some open questions, both computational and combinatorial, concerning reliability polynomials are discussed. 1 The Basics Our goal here is to state some tantalizing open problems concerning...
Non-Stanley Bounds for Network Reliability (1993)
Jason I. Brown, Charles J. Colbourn
Suppose that each edge of a connected graph G of order n is independently operational with probability p; the reliability of G is the probability that the operational edges form a spanning connected...
Reliable Assignments of Processors to Tasks and Factoring on Matroids (1993)
Charles J. Colbourn, Ehab S. Elmallah
In the simple assignment problem, there are n processors, m tasks, and a relation between the processors and tasks; this relation indicates the ability of the processor to perform the task. When the...
Partitioning the edges of a planar graph into two partial k-trees (1988)
Ehab S. Elmallah, Charles J. Colbourn
In this paper we prove two results on partitioning the edges of a planar graph into two partial k-trees, for fixed values of k. Interest in this class of partitioning problems arises since many...
The chromatic index of cyclic Steiner 2-designs (1982)
Charles J. Colbourn, Marlene J. Colbourn
The number of colours needed to colour the blocks of a cyclic Steiner 2-design S(2,k,v) is at most v.
Computing the Chromatic Index of Steiner Triple Systems (1982)
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....
Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays
Myra B. Cohen, Charles J. Colbourn
Steiner triple systems are well studied combinatorial designs that have been shown to possess properties desirable for the construction of multiple erasure codes in RAID architectures. The ordering...
An Upper Bound for Disjunct Matrices
Laura Riccio, Charles J. Colbourn
Erdos, Frankl, and Furedi established an upper bound on the minimum number of rows in a 2-disjunct matrix. We refine their bound, and establish analogous results for 3- and 4-disjunct matrices. 1...
Maximum Kirkman Signal Sets for Synchronous Uni-Polar Multi-User Communication Systems
Charles J. Colbourn, Sufang Zhao
A unipolar signaling system transmits using intensity or amplitude in multiple dimensions. Typical examples arise in optical transmission or radio communication using MT-MFSK as both the signaling...
Concerning Difference Matrices
Charles J. Colbourn, Donald L. Kreher
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...
Kirkman School Project Designs
A Kirkman school project design on v elements consists of the maximum admissible number of disjoint parallel classes, each containing blocks of sizes three except possibly one of size two or four....
Multicast Communication in a Class of Rearrangeable Optical WDM Networks
Chunling Zhou, Yuanyuan Yang, Charles J. Colbourn
Multicast is the ability to transmit information from a single source node to multiple destination nodes. Current trends in networking applications indicate an increasing demand in future networks...
A Framework of Greedy Methods for Constructing Interaction Test Suites
Renee C. Bryce, Charles J. Colbourn, Myra B. Cohen
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....