Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 12/2023

03-09-2023

Scheduling to reduce close contacts: resolvable grid graph decomposition and packing

Authors: Yeow Meng Chee, Alan Chi Hung Ling, Van Khu Vu, Hui Zhang

Published in: Designs, Codes and Cryptography | Issue 12/2023

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Motivated by the COVID-19 pandemic, we consider the scheduling of seating arrangement for an event that is divided into sessions, aiming at reducing the number of close contacts of participants, while the physical and temporal distancing rules are taken into consideration simultaneously. In this paper, we formalize the requirements as a resolvable graph decomposition or packing problem, and focus on the grid graphs defined over vertices that are arranged into arrays embedded in the Euclidean space. We provide explicit constructions of such arrangement, and particularly for those that reach or asymptotically reach the largest possible number of sessions.
previous article Individual discrete logarithm with sublattice reduction
next article Practical attacks on small private exponent RSA: new records and new insights
Literature
1.
Abel R.J.R., Greig M.: BIBDs with small block size. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 72–79. Chapman & Hall/CRC, Boca Raton (2007).
2.
Abel R.J.R., Ge G., Yin J.: Resolvable and near-resolvable designs. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 124–132. Chapman & Hall/CRC, Boca Raton (2007).
3.
4.
Bryant D., Rodger C.: Cycle decompositions. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 373–382. Chapman & Hall/CRC, Boca Raton (2007).
5.
Colbourn C.J., Stinson D.R., Zhu L.: More frames with block size four. J. Comb. Math. Comb. Comput. 23, 3–19 (1997).MathSciNetMATH
6.
Danziger P., Mendelsohn E., Quattrocchi G.: Resolvable decompositions of \(\lambda {K}_n\) into the union of two \(2\)-paths. ARS Comb. 93, 33–49 (2009).MATH
7.
Ge G., Ling A.C.H.: On the existence of resolvable \({K}_4-e\)-designs. J. Comb. Des. 15, 502–510 (2007).CrossRefMATH
8.
Greenhalgh T., Jimenez J.L., Prather K.A., et al.: Ten scientific reasons in support of airborne transmission of SARS-CoV-2. Lancet 397, 1603–1605 (2021).CrossRef
9.
10.
11.
Kirkman T.P.: Query VI. In: Lady’s and Gentleman’s Diary. pp. 48 (1850).
12.
Lenz H., Ringel G.: A brief review on Egmont Köhler’s mathematical work. Discret. Math. 97, 3–16 (1991).CrossRefMATH
13.
Li Y., Yin J.: Resolvable packings of \(K_v\) with \(K_2\times K_c\)’s. J. Comb. Des. 17, 177–189 (2009).CrossRef
14.
Lidl R., Niederreiter H.: Finite Fields, 2nd edn Cambridge University Press, Cambridge (1997).MATH
15.
Lim W.-Y., Tan G.S.E., Htun H.L., et al.: First nosocomial cluster of COVID-19 due to the Delta variant in a major acute care hospital in Singapore: investigations and outbreak response. J. Hosp. Infect. 122, 27–34 (2022).CrossRef
16.
Lu X.-N.: Optimal resolvable \(2\times c\) grid-block coverings. Util. Math. 103, 111–120 (2017).MathSciNetMATH
17.
Lu X.-N., Satoh J., Jimbo M.: Grid-block difference families and related combinatorial structures. Discret. Math. 342, 2023–2032 (2019).MathSciNetCrossRefMATH
18.
Mutoh Y., Jimbo M., Fu H.-L.: A resolvable \(r\times c\) grid-block packing and its application to DNA library screening. Taiwan. J. Math. 8, 713–737 (2004).CrossRefMATH
19.
20.
21.
22.
Wang L.: Completing the spectrum of resolvable \(({K}_4-e)\)-designs. ARS Comb. 105, 289–291 (2012).MATH
23.
Watson O.J., Barnsley G., Toor J., et al.: Global impact of the first year of COVID-19 vaccination: a mathematical modelling study. Lancet Infect. Dis. 22, 1293–1302 (2022).CrossRef
24.
Willett B.J., Grove J., MacLean O.A., et al.: SARS-CoV-2 Omicron is an immune escape variant with an altered cell entry pathway. Nat. Microbiol. 7, 1161–1179 (2022).CrossRef
Metadata
Title
Scheduling to reduce close contacts: resolvable grid graph decomposition and packing
Authors
Yeow Meng Chee
Alan Chi Hung Ling
Van Khu Vu
Hui Zhang
Publication date
03-09-2023
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 12/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-023-01291-9

Other articles of this Issue 12/2023

Designs, Codes and Cryptography 12/2023 Go to the issue

OriginalPaper

Construction of storage codes of rate approaching one on triangle-free graphs

OriginalPaper

Coding and bounds for partially defective memory cells

OriginalPaper

Another look at key randomisation hypotheses

OriginalPaper

On the fourth weight of generalized Reed–Muller codes

OriginalPaper

Practical attacks on small private exponent RSA: new records and new insights

OriginalPaper

Skew differential Goppa codes and their application to Mceliece cryptosystem

Premium Partner

    Image Credits