An Almost Linear-Time Algorithm for Graph Realization
RICE UNIV HOUSTON TX DEPT OF MATHEMATICAL SCIENCES
Pagination or Media Count:
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.
- Theoretical Mathematics