MINIMAL INTERCHANGES OF (0,1)-MATRICES AND DISJOINT CIRCUITS IN A GRAPH

Abstract

It is shown that the minimal number of interchanges necessary to transform one (0,1)-matrix into another equivalent one may be computed from the maximal number of edge-disjoint circuits in a bipartite graph derived from the difference of the matrices. This partially answers a question raised by Ryser. Two (0,1)-matrices are said to be equivalent if their difference has zero row and column sums. They are said to differ by an interchange if they are equivalent and their difference is zero except for a 2x2 minor.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1963
Accession Number
AD0430437

Entities

People

  • David W. Walkup

Organizations

  • Boeing

Tags

DTIC Thesaurus Topics

  • Acquisition
  • Additives (Chemicals)
  • Algorithms
  • Cancellation
  • Computations
  • Corporations
  • Governments
  • Inequalities
  • Inventions
  • Mathematical Analysis
  • Mathematics
  • New Jersey
  • Notation
  • Orientation (Direction)
  • Procurement
  • Scientific Research
  • Sequences

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.