Application of Tolerance Graphs to Combat COVID-19 Pandemic

Tolerance graphs were introduced in 1982 by Golumbic and 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 grap...

Descripción completa

Detalles Bibliográficos
Autores principales: Crnković, Dean, Švob, Andrea
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer Singapore 2021
Materias:
Original Research
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7869775/
https://www.ncbi.nlm.nih.gov/pubmed/33585825
http://dx.doi.org/10.1007/s42979-021-00462-6
Descripción
Sumario:Tolerance graphs were introduced in 1982 by Golumbic and 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.

Ejemplares similares