Gerd H. Fricke, Stephen T. Hedetniemi, David P. Jacobs and
Vilmar Trevisan
Let T be a tree, A its adjacency matrix, and a be a scalar.
We describe a linear-time algorithm for reducing the matrix
aI + A. Applications include computing the rank of A,
finding a maximum matching in T, computing the rank and
determinant of the associated neighborhood matrix, and
computing the characteristic polynomial of A.
Tampilkan postingan dengan label Reducing the Adjacency Matrix of a Tree. Tampilkan semua postingan
Tampilkan postingan dengan label Reducing the Adjacency Matrix of a Tree. Tampilkan semua postingan
Gerd H. Fricke, Stephen T. Hedetniemi, David P. Jacobs and Vilmar Trevisan, Reducing the Adjacency Matrix of a Tree, pp. 34-43
Langganan:
Postingan (Atom)
