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.