A Combinatorial Base for Some Optimal Matroid Intersection Algorithms.

Abstract

E. Lawler has earlier given an algorithm for finding maximum weight intersections for a pair of matroids, using linear programming concepts and constructions to prove its correctness. In this paper another theoretical base for this algorithm is given which depends only on the basic properties of matroids, and which involves no linear programming concepts.

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1974
Accession Number
ADA003832

Entities

People

  • Stein Krogdahl

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Construction
  • Evolutionary Algorithms
  • Heuristic Methods
  • Linear Programming
  • Mathematics
  • Simplex Method

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research