Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons™

Open Access. Powered by Scholars. Published by Universities.®

PDF

1998

Articles 1 - 6 of 6

Full-Text Articles in Discrete Mathematics and Combinatorics

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer Jul 1998

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer

Mathematical Sciences Technical Reports (MSTR)

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP­ complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …

Go to article

New Semiregular Divisible Difference Sets, James A. Davis Jun 1998

New Semiregular Divisible Difference Sets, James A. Davis

Department of Math & Statistics Faculty Publications

We modify and generalize the construction by McFarland (1973) in two different ways to construct new semiregular divisible difference sets (DDSs) with λ1≠0. The parameters of the DDS fall into a family of parameters found in Jungnickel (1982), where his construction is for divisible designs. The final section uses the idea of a K-matrix to find DDSs with a nonelementary abelian forbidden subgroup.

Go to article

Counting Structures In The Möbius Ladder, John P. Mcsorley Apr 1998

Counting Structures In The Möbius Ladder, John P. Mcsorley

Articles and Preprints

The Möbius ladder, Mn, is a simple cubic graph on 2n vertices. We present a technique which enables us to count exactly many different structures of Mn, and somewhat unifies counting in Mn. We also provide new combinatorial interpretations of some sequences, and ask some questions concerning extremal properties of cubic graphs.

Go to article

Proper And Unit Bitolerance Orders And Graphs, Kenneth P. Bogart, Garth Isaak Feb 1998

Proper And Unit Bitolerance Orders And Graphs, Kenneth P. Bogart, Garth Isaak

Dartmouth Scholarship

We say any order ≺ is a tolerance order on a set of vertices if we may assign to each vertex x an interval Ix of real numbers and a real number tx called a tolerance in such a way that x ≺ y if and only if the overlap of Ix and Iy is less than the minimum of tx and ty and the center of Ix is less than the center of Iy. An order is a bitolerance order if and only if there are intervals Ix and …

Go to article

On Distortion And Thickness Of Knots, Robert B. Kusner, John M. Sullivan Jan 1998

On Distortion And Thickness Of Knots, Robert B. Kusner, John M. Sullivan

Robert Kusner

What length of rope (of given diameter) is required to tie a particular knot? Or, to turn the problem around, given an embedded curve, how thick a regular neighborhood of the curve also is embedded? Intuitively, the diameter of the possible rope is bounded by the distance between strands at the closest crossing in the knot. But of course the distance between two points along a curve goes to zero as the points approach each other, so to make the notion precise, we need to exclude some neighborhood of the diagonal.

Go to article

Hadamard Difference Sets In Nonabelian 2-Groups With High Exponent, James A. Davis, Joel E. Iiams Jan 1998

Hadamard Difference Sets In Nonabelian 2-Groups With High Exponent, James A. Davis, Joel E. Iiams

Department of Math & Statistics Faculty Publications

Nontrivial difference sets in groups of order a power of 2 are part of the family of difference sets called Hadamard difference sets. In the abelian case, a group of order 22t + 2 has a difference set if and only if the exponent of the group is less than or equal to 2t + 2. In a previous work (R. A. Liebler and K. W. Smith, in “Coding Theory, Design Theory, Group Theory: Proc. of the Marshall Hall Conf.,” Wiley, New York, 1992), the authors constructed a difference set in a nonabelian group of order …

Go to article