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.
No takes yet. Share an insight, caveat, or question.
Bixby et al. (1988) studied this question.