Nested Dissection for Sparse Nullspace Bases
Stern, Julio M.; Vavasis, Stephen A.
We propose a nested dissection approach to finding a fundamental cycle basis in a planar graph. the cycle basis corresponds to a fundamental nullspace basis of the adjacency matrix. This problem is meant to model sparse null basis computations occurring in a variety of settings. We achieve an O(n**3/2) bound on the nullspace basis size and an O(nlogn) bound on the size in the special case of grid graphs.
computer science; technical report
Previously Published As