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 , the number denotes the minimum cardinality of a subset of which satisfies the following property: every element in this space differs in at most coordinate from a scalar multiple of a vector in . 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 for every odd prime power .

**1.**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**, 10.1007/s11786-007-0028-0**2.**Walter Alexandre Carnielli,*On covering and coloring problems for rook domains*, Discrete Math.**57**(1985), no. 1-2, 9–16. MR**816044**, 10.1016/0012-365X(85)90152-9**3.**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****4.**T. J. Dickson,*On a covering problem concerning abelian groups*, J. London Math. Soc. (2)**3**(1971), 222–232. MR**0272889****5.**Michael R. Garey and David S. Johnson,*Computers and intractability*, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. MR**519066****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.**44**(1969), 60–64. MR**0231734****8.**G. Kéri, Tables for bound on covering codes, homepage: http://www.sztaki.hu/keri/accessed (2011).**9.**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****10.**A.N. Martinhão and E.L. Monte Carmelo, A new exact value on short covering, manuscript in preparation, (2011).**11.**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**, 10.1016/j.dam.2009.11.006**12.**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**, 10.1007/s00010-009-2971-0**13.**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**, 10.1016/j.ejc.2006.09.008**14.**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**, 10.1016/j.aml.2009.09.022**15.**S. K. Zaremba,*A covering theorem for Abelian groups*, J. London Math. Soc.**26**(1951), 71–72. MR**0038967**

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}nm@hotmail.com

**Emerson L. Monte Carmelo**

Affiliation:
Departamento de Matemática, Universidade Estadual de Maringá, Brazil

Email:
elmcarmelo@uem.br

DOI:
http://dx.doi.org/10.1090/S0025-5718-2012-02613-5

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.