Short covering codes arising from matchings in weighted graphs

Martinhão, Anderson; Monte Carmelo, Emerson

doi:10.1090/S0025-5718-2012-02613-5

Short covering codes arising from matchings in weighted graphs
HTML articles powered by AMS MathViewer

by Anderson N. Martinhão and Emerson L. Monte Carmelo PDF

Math. Comp. 82 (2013), 605-616 Request permission

Abstract:

The concept of embedded matching in a weighted graph is introduced, and the maximum cardinality of an embedded matching is computed. On the other hand, consider the following problem induced by a short covering. Given a prime power $q$, the number $c(q)$ denotes the minimum cardinality of a subset $\mathcal {H}$ of $\mathbb {F}_q^3$ which satisfies the following property: every element in this space differs in at most $1$ coordinate from a scalar multiple of a vector in $\mathcal {H}$. As another goal, a connection between embedded matching and short covering code is established. Moreover, this link is applied to improve the upper bound on $c(q)$ for every odd prime power $q$.

References

Satyajit Banerjee, Atish Datta Chowdhury, and Subhas Kumar Ghosh, Efficient algorithms for variants of weighted matching and assignment problems, Math. Comput. Sci. 1 (2008), no. 4, 673–688. MR 2415165, DOI 10.1007/s11786-007-0028-0
Walter Alexandre Carnielli, On covering and coloring problems for rook domains, Discrete Math. 57 (1985), no. 1-2, 9–16. MR 816044, DOI 10.1016/0012-365X(85)90152-9
Gérard Cohen, Iiro Honkala, Simon Litsyn, and Antoine Lobstein, Covering codes, North-Holland Mathematical Library, vol. 54, North-Holland Publishing Co., Amsterdam, 1997. MR 1453577
T. J. Dickson, On a covering problem concerning abelian groups, J. London Math. Soc. (2) 3 (1971), 222–232. MR 272889, DOI 10.1112/jlms/s2-3.2.222
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
I.N. Herstein, Topics in Algebra, J. Wiley & Sons, Singapore, (1993).
J. G. Kalbfleisch and R. G. Stanton, A combinatorial problem in matching, J. London Math. Soc. 44 (1969), 60–64. MR 231734, DOI 10.1112/jlms/s1-44.1.60
G. Kéri, Tables for bound on covering codes, homepage: http://www.sztaki.hu/k̃eri/accessed (2011).
László Lovász and Michael D. Plummer, Matching theory, AMS Chelsea Publishing, Providence, RI, 2009. Corrected reprint of the 1986 original [MR0859549]. MR 2536865, DOI 10.1090/chel/367
A.N. Martinhão and E.L. Monte Carmelo, A new exact value on short covering, manuscript in preparation, (2011).
Carlos Mendes, Emerson L. Monte Carmelo, and Marcus Poggi, Bounds for short covering codes and reactive tabu search, Discrete Appl. Math. 158 (2010), no. 5, 522–533. MR 2592458, DOI 10.1016/j.dam.2009.11.006
E. L. Monte Carmelo and C. F. X. de Mendonça Neto, Extremal problems on sum-free sets and coverings in tri-dimensional spaces, Aequationes Math. 78 (2009), no. 1-2, 101–112. MR 2552526, DOI 10.1007/s00010-009-2971-0
E. L. Monte Carmelo and I. N. Nakaoka, Short coverings in tridimensional spaces arising from sum-free sets, European J. Combin. 29 (2008), no. 1, 227–233. MR 2368629, DOI 10.1016/j.ejc.2006.09.008
I. N. Nakaoka and O. J. N. T. N. dos Santos, A covering problem over finite rings, Appl. Math. Lett. 23 (2010), no. 3, 322–326. MR 2565199, DOI 10.1016/j.aml.2009.09.022
S. K. Zaremba, A covering theorem for Abelian groups, J. London Math. Soc. 26 (1951), 71–72. MR 38967, DOI 10.1112/jlms/s1-26.1.71