Bixby, Robert E.; Wagner, Donald K. An almost linear-time algorithm for graph realization. (English) Zbl 0654.05023 Math. Oper. Res. 13, No. 1, 99-123 (1988). Summary: 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\). Cited in 27 Documents MSC: 05C05 Trees 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) Keywords:planarity testing; network structure; graph-realization problem; tree; algorithm PDF BibTeX XML Cite \textit{R. E. Bixby} and \textit{D. K. Wagner}, Math. Oper. Res. 13, No. 1, 99--123 (1988; Zbl 0654.05023) Full Text: DOI