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
_version_ 1783648694509240320
author Crnković, Dean
Švob, Andrea
author_facet Crnković, Dean
Švob, Andrea
author_sort Crnković, Dean
collection PubMed
description 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.
format Online
Article
Text
id pubmed-7869775
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Springer Singapore
record_format MEDLINE/PubMed
spelling pubmed-78697752021-02-09 Application of Tolerance Graphs to Combat COVID-19 Pandemic Crnković, Dean Švob, Andrea SN Comput Sci Original Research 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. Springer Singapore 2021-02-08 2021 /pmc/articles/PMC7869775/ /pubmed/33585825 http://dx.doi.org/10.1007/s42979-021-00462-6 Text en © The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. part of Springer Nature 2021 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Original Research
Crnković, Dean
Švob, Andrea
Application of Tolerance Graphs to Combat COVID-19 Pandemic
title Application of Tolerance Graphs to Combat COVID-19 Pandemic
title_full Application of Tolerance Graphs to Combat COVID-19 Pandemic
title_fullStr Application of Tolerance Graphs to Combat COVID-19 Pandemic
title_full_unstemmed Application of Tolerance Graphs to Combat COVID-19 Pandemic
title_short Application of Tolerance Graphs to Combat COVID-19 Pandemic
title_sort application of tolerance graphs to combat covid-19 pandemic
topic Original Research
url 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
work_keys_str_mv AT crnkovicdean applicationoftolerancegraphstocombatcovid19pandemic
AT svobandrea applicationoftolerancegraphstocombatcovid19pandemic

Ejemplares similares