An Almost Linear-Time Algorithm for Graph Realization

Abstract

Given a {0, 1}-matrix M, the graph-realization problem for M is to find a tree T 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.