摘要：Let M = (m_{ij}) be a symmetric matrix of order n and let G be the graph with vertex set {1,â¦,n} such that distinct vertices i and j are adjacent if and only if m_{ij} â 0. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to M. If G is given with a tree decomposition ð'¯ of width k, then this can be done in time O(k ð'¯ + k² n), where ð'¯ denotes the number of nodes in ð'¯.
