论文标题
用于计算树木独立性多项式的线性算法
A Linear Algorithm for Computing Independence Polynomials of Trees
论文作者
论文摘要
图中的独立集是一组成对的非贴剂顶点。令$α（g）$表示图$ g =（v，e）$中最大独立集的基数。古特曼（Gutman）和哈里（Harary）定义了$ g $的独立性多项式 \ [ i（g; x）= \ sum_ {k = 0}^{α（g）} {s_k} x^{k} = {s_0}+{s_1}+{s_1} x+{s_2} x^{2} x^{2}+...+...+...+... \] 其中$ s_k $表示图形$ g $中的独立基数$ k $的独立集数量。关于该主题的全面调查是由于Levit和Mandrescu引起的，其中一些递归公式允许计算独立性多项式。这些递归的直接实施不会带来有效的算法。 Yosef，Mizrachi和Kadrawi开发了一种有效的方法来计算具有$ n $顶点的树木的独立性多项式，以便需要一个包含所有树木的所有独立性多项式的数据库，最多需要$ N-1 $ VERTICES。这种方法不适合大树，因为需要大量数据库。另一方面，使用动态编程，可以开发一种有效的算法来防止重复计算。总而言之，我们的动态编程算法在线性时间内在树上运行，不取决于数据库。
An independent set in a graph is a set of pairwise non-adjacent vertices. Let $α(G)$ denote the cardinality of a maximum independent set in the graph $G = (V, E)$. Gutman and Harary defined the independence polynomial of $G$ \[ I(G;x) = \sum_{k=0}^{α(G)}{s_k}x^{k}={s_0}+{s_1}x+{s_2}x^{2}+...+{s_{α(G)}}x^{α(G)}, \] where $s_k$ denotes the number of independent sets of cardinality $k$ in the graph $G$. A comprehensive survey on the subject is due to Levit and Mandrescu, where some recursive formulas are allowing to calculate the independence polynomial. A direct implementation of these recursions does not bring about an efficient algorithm. Yosef, Mizrachi, and Kadrawi developed an efficient way for computing the independence polynomials of trees with $n$ vertices, such that a database containing all of the independence polynomials of all the trees with up to $n-1$ vertices is required. This approach is not suitable for big trees, as an extensive database is needed. On the other hand, using dynamic programming, it is possible to develop an efficient algorithm that prevents repeated calculations. In summary, our dynamic programming algorithm runs over a tree in linear time and does not depend on a database.
