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
Additional Information
- Anderson N. Martinhão
- Affiliation: Departamento de Matemática, Universidade Estadual de Maringá, Brazil
- Email: and_nm@hotmail.com
- Emerson L. Monte Carmelo
- Affiliation: Departamento de Matemática, Universidade Estadual de Maringá, Brazil
- Email: elmcarmelo@uem.br
- Received by editor(s): April 12, 2011
- Received by editor(s) in revised form: August 24, 2011
- Published electronically: May 1, 2012
- Additional Notes: The first author was supported by Capes.
The second author is supported by Fundação Araucária and CNPq. - © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 82 (2013), 605-616
- MSC (2010): Primary 11B75, 05C70, 94B75; Secondary 05B40, 11T71, 94B25
- DOI: https://doi.org/10.1090/S0025-5718-2012-02613-5
- MathSciNet review: 2983038
Dedicated: This work is dedicated to Professor Adilson Gonçalves