An algorithm for calculating the independence and vertex-cover polynomials of a graph |
| |
Authors: | Gordon G Cash |
| |
Institution: | aNew Chemicals Screening and Assessment Branch, Risk Assessment Division (7403M), US Environmental Protection Agency, 1200 Pennsylvania Avenue, N. W., Washington, DC 20460, United States |
| |
Abstract: | The independence polynomial, ω(G,x)=∑wkxk, of a graph, G, has coefficients, wk, that enumerate the ways of selecting k vertices from G so that no two selected vertices share an edge. The independence number of G is the largest value of k for which wk≠0. Little is known of less straightforward relationships between graph structure and the properties of ω(G,x), in part because of the difficulty of calculating values of wk for specific graphs. This study presents a new algorithm for these calculations which is both faster than existing ones and easily adaptable to high-level computer languages. |
| |
Keywords: | Independence polynomial Graph polynomial Independence number Vertex-cover polynomial |
本文献已被 ScienceDirect 等数据库收录! |
|