Accession Number:

ADA455177

Title:

An Almost Linear-Time Algorithm for Graph Realization

Descriptive Note:

Technical rept.

Corporate Author:

RICE UNIV HOUSTON TX DEPT OF MATHEMATICAL SCIENCES

Personal Author(s):

• Bixby, Robert E.
• Wagner, Donald K.

Report Date:

1985-03-01

Pagination or Media Count:

41.0

Abstract:

Given a 0, 1-matrix M, the graph realization problem for M is to find a tree such that the columns of M are incidence vectors of paths in T, or to show that no such T exists. An algorithm is presented for this problem the time complexity of which is very nearly linear in the number of ones in M.

Descriptors:

• *GRAPHS
• *MATRIX THEORY
• ALGORITHMS
• LINEAR PROGRAMMING
• LINEARITY

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE