# 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):

# 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:

# Subject Categories:

- Theoretical Mathematics