Open Access is an initiative that aims to make scientific research freely available to all. To date our community has made over 100 million downloads. It’s based on principles of collaboration, unobstructed discovery, and, most importantly, scientific progression. As PhD students, we found it difficult to access the research we needed, so we decided to create a new Open Access publisher that levels the playing field for scientists across the world. How? By making research easy to access, and puts the academic needs of the researchers before the business interests of publishers.
We are a community of more than 103,000 authors and editors from 3,291 institutions spanning 160 countries, including Nobel Prize winners and some of the world’s most-cited researchers. Publishing on IntechOpen allows authors to earn citations and find new collaborators, meaning more people see your work not only from your own field of study, but from other related fields too.
By Ohr Kadrawi, Vadim E. Levit, Ron Yosef and Matan Mizrachi
An independent set in a graph is a set of pairwise nonadjacent vertices. Let αG denote the cardinality of a maximum independent set in the graph G=VE. In 1983, Gutman and Harary defined the independence polynomial of GIGx=∑k=0αGskxk=s0+s1x+s2x2+…+sαGxαG, where sk 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 computation of the independence polynomial. A direct implementation of these recursions does not bring about an efficient algorithm. In 2021, 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.