TRANSVERSALS AND MATROID PARTITION

Abstract

A matroid M = (E, F) is a finite set E of elements and a family F of subsets of E, called independent sets, such that (1) every subset of an independent set is independent, and (2) for every set A belonging to E, all maximal independent subsets of A have the same cardinality, called the rank r(A) of A. The concept of 'matroid' thus generalizes that of 'matrix' or, in particular, that of 'graph.' This paper treats a variety of partition problems involving independent sets of matroids.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1965
Accession Number
AD0615663

Entities

People

  • D. R. Fulkerson
  • Jack Edmonds

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Applied Mathematics
  • Coverings
  • Equations
  • Families (Human)
  • Graph Theory
  • Inequalities
  • Integrals
  • Language
  • Materials
  • Mathematics
  • Military Research
  • Truncation
  • United States

Readers

  • Graph Algorithms and Convex Optimization.