Framework for Prioritizing Contact Tracing and Mass Testing of COVID-19 Using Graph Theory

Main Article Content

Obed Appiah
Dominic Otoo
Christopher Bombie Ninfaakang


Contact tracing has become one of the most useful tools for fighting the novel Corona Virus (COVID-19) pandemic worldwide. The underlining philosophy of contact tracing is determining people who have been in contact with infected persons and thus isolate them from becoming agents of onward transmission of the virus.  Slow tracing of contacts and inconsistent or inaccurate information provided by patients usually leads to the spread of the virus along a trajectory at the healthcare systems' blindside. This has led to the proposal of app-based contact tracing solutions.  This paper proposes an SQL-based framework that transforms simple interaction data entries into interaction graphs and applies graph theory to prioritize the contact tracing process. The framework returns nodes or individual IDs together with values called Risk_Points to enable individuals' selection for isolation and treatment. Results on simulated data show that the proposed framework can help slow the virus's rate of transmission.

SQL-based framework, graph-theory risk points, contact tracing, COVID-19 testing.

Article Details

How to Cite
Appiah, O., Otoo, D., & Ninfaakang, C. B. (2021). Framework for Prioritizing Contact Tracing and Mass Testing of COVID-19 Using Graph Theory. Asian Journal of Research in Computer Science, 7(1), 50-66.
Original Research Article


Abeler J, Bäcker M, Buermeyer U, Zillessen H. COVID-19 contact tracing and data protection can go together. JMIR mHealth and uHealth. 2020; 8(4).

Park O, Park YJ, Kim SY, Kim J, Lee J, Yum M. Contact transmission of COVID-19 in South Korea: Novel investigation techniques for tracing contacts. Osong Public Health and Research Perspectives. 2020;11(1):60–63,

Ferretti L, Wymant C, Kendall M, Zhao L, Nurtay A, Abeler-Dorner L, Parker M, Bonsall DG, and C. Fraser. Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing; 2020.

Saurabh S, Prateek S. Role of contact tracing in containing the 2014 Ebola outbreak: A review. African Health Sciences. 2017;17(1):225.

Martínez MJ, Salim AM, Hurtado JC, Kilgore PE. Ebola virus infection: Overview and update on prevention and treatment. Infectious Diseases and Therapy, 2015; 4(4):365–390.

Olu OO, Lamunu M, Nanyunja M, Dafae F, Samba T, Sempiira N et al. Contact tracing during an outbreak of ebola virus disease in the western area districts of Sierra Leone: Lessons for future ebola outbreak response. Frontiers in Public Health. 2016;4.

Danquah LO, Hasham N, Macfarlane M, Conteh FE, Momoh F, Tedesco AA et al. Use of a mobile application for Ebola contact tracing and monitoring in northern Sierra Leone: A proof-of-concept study. BMC Infectious Diseases. 2019;19(1).

Cheng HY, Jian SW, Liu DP, Ng TC, Huang WT, Lin HH. Contact tracing assessment of COVID-19 transmission dynamics in taiwan and risk at different exposure periods before and after symptom onset. JAMA Internal Medicine; 2020.

He Z. What further should be done to control COVID-19 outbreaks in addition to cases isolation and contact tracing measures? BMC Medicine. 2020;18(1).

Yasaka TM. Lehrich BM, Sahyouni R. Peer-to-peer contact tracing: Development of a privacy-preserving smartphone app (Preprint); 2020.

Trace together.
Accessed: 22-Jun-2020.

Poojary T. Coronavirus: Apple and google to partner for contact tracing technology; 2020.
Accessed: 22-Jun-2020.

Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. MIT Press. Cambridge. MA. 2nd edition; 2001.

Bryant V, Wallis WD. A beginner's guide to graph theory, the mathematical gazette. 2001;85(503):374.

SSG, Vetrivel S, ENM. Applications of graph theory in computer science an overview. International Journal of Engin eering Science and Technology. 2010; 2(9):4610–4621.

Darvish M, Yasaei M, Saeedi A. Application of the graph theory and matrix methods to contractor ranking. International Journal of Project Manage ment. 2009;27(6):610–619.

Otoo D, Amponsah SK, Sebil C. Capacitated clustering and collection of solid waste in Kwadaso estate, Kumasi. Journal of Asian Scientific Research, 2014; 4(8):460–472.

Keeling MJ, Hollingsworth TD, Read JM. The efficacy of contact tracing for the containment of the 2019 novel corona virus (COVID-19); 2020.

Coronavirus disease (COVID-19) - Events as they happen. World Health Organi zation.
Accessed: 22-Jun-2020.

Dropkin G. Covid-19: Contact tracing requires ending the hostile environment. Bmj p. m1320; 2020.