Premium
Parallel algorithm for the computation of characteristic polynomials of chemical graphs
Author(s) -
Venuvanalingam P.,
Thangavel P.
Publication year - 1991
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/jcc.540120702
Subject(s) - algorithm , computation , frame (networking) , parallel algorithm , computer science , time complexity , running time , mathematics , combinatorics , telecommunications
A parallel algorithm is developed for the first time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O ( n 3 ) processors whereas the sequential algorithm takes O ( n 4 ) time. Especially when the number of vertices of the graph is large this method will be more efficient than the recently developed vectorized Frame and Givens–Householder methods.