engleski

Application of tolerance graphs to combat COVID-19 pandemic

Tolerance graphs were introduced in 1982 by M. C. Golumbic and C. L. Monma as a generalization of interval graphs. In this paper we propose several applications of tolerance graphs in fighting COVID-19. These applications include finding cliques of a certain size and calculating the chromatic number of a graph, the problems that are in general NP-complete but for tolerance graphs can be solved in polynomial time.

pandemic ; tolerance graph ; perfect graph ; chromatic number ; clique

nije evidentirano