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:

## ADA455177

# Title:

## An Almost Linear-Time Algorithm for Graph Realization

# Descriptive Note:

## Technical rept.

# Corporate Author:

## RICE UNIV HOUSTON TX DEPT OF MATHEMATICAL SCIENCES

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

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#