An Almost Linear-Time Algorithm for Graph Realization
Robert E. Bixby, Donald K. Wagner · Mathematics of Operations Research · 1988
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.