Project duration: 2016-2018
Project coordinator: University of Kuwait, Kuwait
Participants from Singidunum University: Dejan Živković
The characteristic polynomial of any square matrix of order can be computed in time by the standard algorithm. So, the same applies for computing the characteristic polyno0mial of graphs of order For some special classes of graphs, however, like threshoild and chaim graphs, the time complexity bound can be significantly improved by the exploiting their combinational structure. For example, for threshold graphs the bound is recently decreased to. Here we put forward some novel ideas based on the divisor technique to obtain another fast algorithm for computing the characteristic polynomial of threshold and chain graphs, as well as some other graph classes.