DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# Accession Number:

## ADA247400

# Title:

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

# Descriptive Note:

## Technical rept.

# Corporate Author:

## CARNEGIE-MELLON UNIV PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION

# Report Date:

## 1991-10-01

# Pagination or Media Count:

##
25.0

# 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 4k2 2 The graph G has a chordless cycle of length 4k2, 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.

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#