Linear algorithms for the Hosoya index and Hosoya matrix of a treeVesel, Aleksander (Avtor) Hosoya indexHosoya matrixoptimal algorithmThe Hosoya index of a graph is defined as the total number of its independent edge sets. This index is an important example of topological indices, a molecular-graph based structure descriptor that is of significant interest in combinatorial chemistry. The Hosoya index inspires the introduction of a matrix associated with a molecular acyclic graph called the Hosoya matrix. We propose a simple linear-time algorithm, which does not require pre-processing, to compute the Hosoya index of an arbitrary tree. A similar approach allows us to show that the Hosoya matrix can be computed in constant time per entry of the matrix.MDPI20212024-05-30 03:29:20Znanstveno delo88848sl