English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

An independent set in a graph is a set of pairwise non-adjacent vertices. Let$\alpha(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}^{\alpha(G)}{s_k}x^{k}={s_0}+{s_1}x+{s_2}x^{2}+...+{s_{\alpha(G)}}x^{\alpha(G)},  \]  where $s_k$ denotes the number of independent sets of cardinality $k$ in thegraph $G$. A comprehensive survey on the subject is due to Levit and Mandrescu,where some recursive formulas are allowing to calculate the independencepolynomial. A direct implementation of these recursions does not bring about anefficient algorithm. Yosef, Mizrachi, and Kadrawi developed an efficient wayfor computing the independence polynomials of trees with $n$ vertices, suchthat a database containing all of the independence polynomials of all the treeswith up to $n-1$ vertices is required. This approach is not suitable for bigtrees, as an extensive database is needed. On the other hand, using dynamicprogramming, it is possible to develop an efficient algorithm that preventsrepeated calculations. In summary, our dynamic programming algorithm runs overa tree in linear time and does not depend on a database.

A Linear Algorithm for Computing Independence Polynomials of Trees