College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
|Title: ||Nested Dissection for Sparse Nullspace Bases|
|Authors: ||Stern, Julio M.|
Vavasis, Stephen A.
|Keywords: ||computer science|
|Issue Date: ||Dec-1990|
|Publisher: ||Cornell University|
|Abstract: ||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.|
|Appears in Collections:||Computer Science Technical Reports|
Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.