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

Personal Author(s):

• Conforti, Michele
• Cornuejols, Gerard
• Rao, M. R.

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.

Descriptors:

• *POLYNOMIALS
• REMOVAL
• RECOGNITION
• NODES
• ALGORITHMS
• EDGES

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE