Decomposition of Balanced Matrices. Part 7. A Polynomial Recognition Algorithm

Abstract

In this seven part paper, we prove the following theorem: At least one of the following alternatives occurs for a bipartite graph G: (1) The graph G has no cycle of length 4k+2; (2) The graph G has a chordless cycle of length 4k+2, (3) There exist two complete bipartite graphs K sub 1, K sub 2 in G having disjoint node sets, with the property that the removal of the edges in K sub 1, K sub 2 disconnects G; and (4) There exists a subset S of the nodes of G with the property that the removal of S disconnects G, where S can be partitioned into three disjoint sets T,A,N.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1991
Accession Number
ADA247400

Entities

People

  • Gérard Cornuéjols
  • M. R. Rao
  • Michele Conforti

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Contracts
  • Decomposition
  • Heuristic Methods
  • Identification
  • Integer Programming
  • Military Research
  • New York
  • Optimization
  • Polynomials
  • Recognition
  • Sequences
  • Students
  • Symmetry
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.