×

Group testing with geometry of classical groups over finite fields. (English) Zbl 1416.05304

Summary: In this paper, we give an overview of combinatorial group testing and algebra. Our survey focuses on the constructions with algebraic methods, especially geometry of classical groups over finite fields.

MSC:

05E30 Association schemes, strongly regular graphs
05B30 Other designs, configurations
20G40 Linear algebraic groups over finite fields
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Du, D.; Hwang, FK, Combinatorial Group Testing and Its Applications (2000), Singapore: World Scientific, Singapore · Zbl 0952.90001
[2] D’yachkov, AG; Hwang, FK; Macula, AJ; Vilenkin, PA; Weng, C., A construction of pooling designs with some happy surprises, J. Comput. Biol., 12, 1129-1136 (2005) · doi:10.1089/cmb.2005.12.1129
[3] Erdös, P.; Frankl, P.; Füredi, D., Families of finite sets in which no set is covered by the union of \(r\) others, Israel J. Math., 51, 79-89 (1985) · Zbl 0587.05021 · doi:10.1007/BF02772959
[4] Guo, J., Pooling designs associated with unitary space and ratio efficiency comparison, J. Comb. Optim., 19, 492-500 (2010) · Zbl 1201.90170 · doi:10.1007/s10878-008-9185-6
[5] Guo, J.; Wang, KS, A construction of pooling designs with surprisingly high degree of error correction, J. Combin. Theory Ser. A, 118, 2056-2058 (2011) · Zbl 1232.05044 · doi:10.1016/j.jcta.2011.04.008
[6] Guo, J.; Wang, KS, Pooling designs with surprisingly high degree of error correction in a finite vector space, Discrete Appl. Math., 160, 2172-2176 (2012) · Zbl 1251.05027 · doi:10.1016/j.dam.2012.05.018
[7] Guo, J.; Wang, KS; Weng, CW, Pooling semilattices and non-adaptive pooling designs, Discrete Math., 320, 64-72 (2014) · Zbl 1281.05035 · doi:10.1016/j.disc.2013.12.004
[8] Guo, J.; Wang, YX; Gao, SG; Yu, JC; Wu, WL, Constructing error-correcting pooling designs with symplectic space, J. Comb. Optim., 20, 413-421 (2010) · Zbl 1206.90143 · doi:10.1007/s10878-009-9217-x
[9] Gao, SG; Li, ZT; Du, HJ; Shi, Y.; Wu, WL, Approaching pooling design with smaller efficient ratio, J. Global Optim., 49, 125-135 (2011) · Zbl 1252.90071 · doi:10.1007/s10898-010-9538-4
[10] Gao, SG; Li, ZT; Yu, JC; Gao, XF; Wu, WL, DNA library screening, pooling design and unitary spaces, Theor. Comput. Sci., 412, 217-224 (2011) · Zbl 1204.92034 · doi:10.1016/j.tcs.2009.06.004
[11] Guo, HX; Nan, JZ, Construction of error-tolerance pooling designs in symplectic spaces, J. Global Optim., 58, 405-410 (2014) · Zbl 1415.05031 · doi:10.1007/s10898-013-0049-y
[12] Huang, TY; Weng, CW, Pooling spaces and non-adaptive pooling designs, Discrete Math., 282, 163-169 (2004) · Zbl 1045.06001 · doi:10.1016/j.disc.2003.11.004
[13] Huang, TY; Wang, KS; Weng, CW, Pooling spaces associated with finite geometry, European J. Combin., 29, 1483-1491 (2008) · Zbl 1195.92075 · doi:10.1016/j.ejc.2007.06.017
[14] Kautz, WH; Singleton, RC, Nonadaptive binary superimposed codes, IEEE Trans. Inform. Theory, 10, 363-377 (1964) · Zbl 0133.12402 · doi:10.1109/TIT.1964.1053689
[15] Lang, W.; Wang, Y.; Yu, J.; Gao, SG; Wu, WL, Error-tolerant trivial two-stage group testing for complexes using almost separable almost disjunct martrices, Discrete Math. Algorithms Appl., 1, 235-251 (2009) · Zbl 1189.05040 · doi:10.1142/S1793830909000191
[16] Li, ZT; Huang, TY; Gao, SG, Two error-correcting pooling designs from symplectic spaces over a finite field, Linear Algebra Appl., 433, 1138-1147 (2010) · Zbl 1214.90101 · doi:10.1016/j.laa.2010.04.040
[17] Li, ZT; Gao, SG; Du, HJ; Zou, F.; Wu, WL, Two constructions of new error-correcting pooling design from orthogonal spaces over finite field of characteristic 2, J. Comb. Optim., 20, 325-334 (2010) · Zbl 1206.90148 · doi:10.1007/s10878-009-9210-4
[18] Li, ZT; Gao, SG; Du, HJ; Zou, F.; Wu, WL, Efficient error-correcting pooling designs constructed from pseudo-symplictic spaces over a finite field, J. Comput. Biol., 17, 1413-1423 (2010) · doi:10.1089/cmb.2008.0206
[19] Liu, XM; Gao, Y., Constructing error-correcting pooling designs with singular linear space, J. Combin. Math. Combin. Comput., 87, 267-274 (2013) · Zbl 1291.05031
[20] Liu, XM; Gao, X., New error-correcting pooling designs with vector spaces over finite field, Discrete Math., 338, 857-862 (2015) · Zbl 1371.05041 · doi:10.1016/j.disc.2015.01.003
[21] Macula, AJ, A simple construction of \(d\)-disjunct matrices with certain constant weights, Discrete Math., 162, 311-312 (1996) · Zbl 0870.05012 · doi:10.1016/0012-365X(95)00296-9
[22] Macula, AJ, Error-correcting nonadaptive group testing with \(d^e\)-disjunct matrices, Discrete Appl. Math., 80, 217-222 (1997) · Zbl 0902.94030 · doi:10.1016/S0166-218X(97)80002-9
[23] Macula, AJ, Probabilistic nonadaptive and two-stage group testing with relatively small pools and DNA library screening, J. Comb. Optim., 2, 385-397 (1998) · Zbl 1002.92551 · doi:10.1023/A:1009732820981
[24] Macula, AJ; Gal, S.; Andam, C.; Bishop, MA; Renz, TE, PCR nonadaptive group testing of DNA libraries for biomolecular computing and taggant applications, Discrete Math. Algorithms Appl., 1, 59-69 (2009) · Zbl 1171.92323 · doi:10.1142/S1793830909000051
[25] Nan, JZ; Guo, J., New error-correcting pooling designs associated with finite vector spaces, J. Comb. Optim., 20, 96-100 (2010) · Zbl 1201.05018 · doi:10.1007/s10878-008-9197-2
[26] Ngo, H.; Du, D., A survey on combinatorial group testing algorithms with applications to DNA library screening, Discrete Math. Theor. Comput. Sci., 55, 171-182 (2000) · Zbl 1133.92302 · doi:10.1090/dimacs/055/13
[27] Ngo, H.; Du, D., New constructions of non-adaptive and error-tolerance pooling designs, Discrete Math., 243, 161-170 (2002) · Zbl 0989.05020 · doi:10.1016/S0012-365X(00)00465-9
[28] Park, H.; Wu, W.; Liu, Z.; Wu, X.; Zhao, HG, DNA screening, pooling design and simplicial complex, J. Comb. Optim., 7, 4, 389-394 (2003) · Zbl 1058.05014 · doi:10.1023/B:JOCO.0000017388.06583.04
[29] van Lint, JH; Wilson, RM, A Course in Combinatorics (1992), Victoria: Cambridge, Victoria · Zbl 0769.05001
[30] Wan, ZX, Geometry of Classical Groups Over Finite Fields (2002), Beijing: Science Press, Beijing
[31] Wang, KS; Guo, J.; Li, F., Singular linear space and its applications, Finite Fields Appl., 17, 395-406 (2011) · Zbl 1234.51008 · doi:10.1016/j.ffa.2011.02.001
[32] Yakir, A., Inclusion matrix of \(k\) vs \(1\) affine subspaces and a permutation module of the general affine group, J. Combin. Theory Ser. A, 63, 301-317 (1993) · Zbl 0778.05026 · doi:10.1016/0097-3165(93)90062-D
[33] Zhang, GS; Li, BL; Sun, XL; Li, F., A construction of \(d^z\)-disjunct matrices in a dual space of symplectic space, Discrete Appl. Math., 156, 2400-2406 (2008) · Zbl 1368.15035 · doi:10.1016/j.dam.2007.11.003
[34] Zhang, GS; Sun, XL; Li, BL, Error-correcting pooling designs associated with the dual space of unitary space and ratio efficiency comparison, J Comb. Optim., 18, 51-63 (2009) · Zbl 1260.05029 · doi:10.1007/s10878-007-9137-6
[35] Zhang, GS; Yang, YQ; Zhao, XH, A construction of \(d^z\)-disjunct matrices by orthogonal space and discussion on their design parameters, Discrete Math., 309, 6026-6034 (2009) · Zbl 1292.05067 · doi:10.1016/j.disc.2009.05.001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.