Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


Short covering codes arising from matchings in weighted graphs

Authors: Anderson N. Martinhão and Emerson L. Monte Carmelo
Journal: Math. Comp. 82 (2013), 605-616
MSC (2010): Primary 11B75, 05C70, 94B75; Secondary 05B40, 11T71, 94B25
Published electronically: May 1, 2012
MathSciNet review: 2983038
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. S. Banerjee, A. Datta Chowdhury, and S.K. Ghosh, Efficient algorithms for variants of weighted matching and assignment problems, Math. Comput. Sci., vol. 1 (2008), 673-688. MR 2415165 (2009i:68102)
  • 2. W.A. Carnielli, On covering and coloring problems for rook domains, Discrete Math., vol. 57 (1985), 9-16. MR 816044 (86m:05033)
  • 3. G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes, North-Holland, Amsterdam, (1997). MR 1453577 (99b:94059)
  • 4. T.J. Dickson, A covering problem concerning abelian groups, J. London Math. Soc., vol. 3 (1971), 222-232. MR 0272889 (42:7770)
  • 5. M. Garey and D. Johnson, Computers and intractability: a guide to the theory of NP-completeness, W.H. Freeman and Company, (1979). MR 519066 (80g:68056)
  • 6. I.N. Herstein, Topics in Algebra, J. Wiley & Sons, Singapore, (1993).
  • 7. J.G. Kalbfleisch and R.G. Stanton, A Combinatorial Problem in Matching, J. London Math. Soc., vol. 44 (1969), 60-64. MR 0231734 (38:62)
  • 8. G. Kéri, Tables for bound on covering codes, homepage: (2011).
  • 9. L. Lovász and M.D. Plummer, Matching theory, AMS Chelsea Publishing, Providence, (2009). MR 2536865
  • 10. A.N. Martinhão and E.L. Monte Carmelo, A new exact value on short covering, manuscript in preparation, (2011).
  • 11. C. Mendes, E.L. Monte Carmelo, and M.V. Poggi de Aragão, Bounds for short covering codes and reactive tabu search, Discrete Appl. Math. vol. 158 (2010), 522-533. MR 2592458 (2011f:94164)
  • 12. E.L. Monte Carmelo and C.F.X. De Mendonça Neto, Extremal problems on sum-free sets and coverings in tridimensional spaces, Aequationes Mathematicae, vol. 78 (2009), 101-112. MR 2552526 (2010i:11100)
  • 13. E.L. Monte Carmelo and I.N. Nakaoka, Short coverings in tridimensional spaces arising from sum-free sets, European J. Combin., vol. 29 (2008), 227-233. MR 2368629 (2008j:11081)
  • 14. I.N. Nakaoka and O.J.N.T.N. Santos, A covering problem over finite rings, Appl. Math. Letters, vol. 23 (2010), 322-326. MR 2565199 (2011e:13049)
  • 15. S.K. Zaremba, A covering theorem for abelian groups, J. London Math. Soc., vol. 26 (1951), 71-72. MR 0038967 (12:477a)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11B75, 05C70, 94B75, 05B40, 11T71, 94B25

Retrieve articles in all journals with MSC (2010): 11B75, 05C70, 94B75, 05B40, 11T71, 94B25

Additional Information

Anderson N. Martinhão
Affiliation: Departamento de Matemática, Universidade Estadual de Maringá, Brazil
Email: and{\textunderscore}

Emerson L. Monte Carmelo
Affiliation: Departamento de Matemática, Universidade Estadual de Maringá, Brazil

Keywords: Matching, weighted graph, square number, finite field, independent vectors, covering codes.
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.
Dedicated: This work is dedicated to Professor Adilson Gonçalves
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society