# zbMATH — the first resource for mathematics

An almost linear-time algorithm for graph realization. (English) Zbl 0654.05023
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$$.

##### MSC:
 05C05 Trees 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
Full Text: