TRANSVERSAL PACKINGS AND COVERS

Abstract

Let S sub 1, S sub 2, S sub M be a collection of subsets of a finite set S. The subset T of S is a partial transversal of size t of the subsets S sub 1, S sub 2, S sub M if (i) T consists of t elements of S, and (ii) the term rank of the incidence matrix of S sub 1, S sub 2, S sub M vs. elements of T is equal to t. Necessary and sufficient conditions in order that S sub 1, S sub 2, S sub M have mutually disjoint partial transversals T sub 1, T sub 2, T sub P of sizes t sub 1, t sub 2, t sub P are known. This memorandum shows that the problem of constructing such a transversal packing can be formulated in terms of flows in networks, and existence conditions obtained from results in network flow theory. A similar approach is presented for an analogous covering problem involving partial transversals of prescribed sizes. Finally, connections are indicated between these problems and some recent results of Edmonds in matroid theory. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1965
Accession Number
AD0610556

Entities

People

  • D. R. Fulkerson

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Coverings
  • Decomposition
  • Hard Copy
  • Inequalities
  • Integrals
  • Mathematics
  • Notation
  • Permutations
  • United States

Readers

  • Graph Algorithms and Convex Optimization.