Accession Number:

ADA247462

Title:

Decomposition of Balanced Matrices. Part 5: Goggles

Descriptive Note:

Management sciences research 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:

52.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 - The graph G has no cycle of length 4k2. - The graph G has a chordless cycle of length 4k2. There exist two complete bipartite graphs K1,K2 in G having disjoint node sets, with the property that the removal of the edges in K1,K2 disconnects G. 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 such that T, some node T is adjacent to every node in A N and, ifT equals or more than 2, then A equals or more than 2 and every node of T is adjacent to every node of A. A 0,1 matrix is balanced if it does not contain a square submatrix of odd order with two ones per row and per column. Balanced matrices are important in integer programming and combinatorial optimization since the associated set packing and set covering polytopes have integral vertices.

Descriptors:

• *MATRICES(MATHEMATICS)
• *DECOMPOSITION
• *GOGGLES
• GRAPHS
• INTEGRALS
• INTEGER PROGRAMMING
• CYCLES
• NODES
• LENGTH
• COVERINGS
• PAPER
• EDGES
• THEOREMS
• REMOVAL
• OPTIMIZATION

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE