×

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.)
PDF BibTeX XML Cite
Full Text: DOI