Fast algorithms for computing the characteristic polynomial of some graph classes

Project duration: 2016-2018

Project coordinator: University of Kuwait, Kuwait

Participants from Singidunum University: Dejan Živković

Abstract 

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.