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.
Cited by 73 works. doi:10.1287/moor.13.1.99
Authors
References
- Graph Theory with Applications
- Linear graphs and electrical networks
- Connectivity in Graphs
- Dividing a Graph into Triconnected Components
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Algorithms for network programming
- 2-Isomorphic Graphs
- A Combinatorial Decomposition Theory
- A linear-time algorithm for a special case of disjoint set union
- An Algorithm for Determining Whether a Given Binary Matroid is Graphic