The determinant of a tree's neighborhood
β
David P. Jacobs; Vilmar Trevisan
π
Article
π
1997
π
Elsevier Science
π
English
β 517 KB
Let N be an n Γ n neighborhood matrix for a tree or forest. We show that IdetNI is bounded by the nth Fibonacci number. We obtain a simple, elegant algorithm to compute detN that operates directly on the forest and uses O(n) space and O(n) arithmetic operations.