Short covering codes arising from matchings in weighted graphs
Authors:
Anderson N. Martinhão and Emerson L. Monte Carmelo
Journal:
Math. Comp. 82 (2013), 605616
MSC (2010):
Primary 11B75, 05C70, 94B75; Secondary 05B40, 11T71, 94B25
Published electronically:
May 1, 2012
MathSciNet review:
2983038
Fulltext 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
(2009i:68102), 10.1007/s1178600700280
 2.
Walter
Alexandre Carnielli, On covering and coloring problems for rook
domains, Discrete Math. 57 (1985), no. 12,
9–16. MR
816044 (86m:05033), 10.1016/0012365X(85)901529
 3.
Gérard
Cohen, Iiro
Honkala, Simon
Litsyn, and Antoine
Lobstein, Covering codes, NorthHolland Mathematical Library,
vol. 54, NorthHolland Publishing Co., Amsterdam, 1997. MR 1453577
(99b:94059)
 4.
T.
J. Dickson, On a covering problem concerning abelian groups,
J. London Math. Soc. (2) 3 (1971), 222–232. MR 0272889
(42 #7770)
 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 NPcompleteness;
A Series of Books in the Mathematical Sciences. 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. 44 (1969), 60–64. MR 0231734
(38 #62)
 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
(2011f:94164), 10.1016/j.dam.2009.11.006
 12.
E.
L. Monte Carmelo and C.
F. X. de Mendonça Neto, Extremal problems on sumfree sets
and coverings in tridimensional spaces, Aequationes Math.
78 (2009), no. 12, 101–112. MR 2552526
(2010i:11100), 10.1007/s0001000929710
 13.
E.
L. Monte Carmelo and I.
N. Nakaoka, Short coverings in tridimensional spaces arising from
sumfree sets, European J. Combin. 29 (2008),
no. 1, 227–233. MR 2368629
(2008j:11081), 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
(2011e:13049), 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
(12,477a)
 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), 673688. MR 2415165 (2009i:68102)
 2.
 W.A. Carnielli, On covering and coloring problems for rook domains, Discrete Math., vol. 57 (1985), 916. MR 816044 (86m:05033)
 3.
 G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes, NorthHolland, Amsterdam, (1997). MR 1453577 (99b:94059)
 4.
 T.J. Dickson, A covering problem concerning abelian groups, J. London Math. Soc., vol. 3 (1971), 222232. MR 0272889 (42:7770)
 5.
 M. Garey and D. Johnson, Computers and intractability: a guide to the theory of NPcompleteness, 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), 6064. MR 0231734 (38:62)
 8.
 G. Kéri, Tables for bound on covering codes, homepage: http://www.sztaki.hu/keri/accessed (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), 522533. MR 2592458 (2011f:94164)
 12.
 E.L. Monte Carmelo and C.F.X. De Mendonça Neto, Extremal problems on sumfree sets and coverings in tridimensional spaces, Aequationes Mathematicae, vol. 78 (2009), 101112. MR 2552526 (2010i:11100)
 13.
 E.L. Monte Carmelo and I.N. Nakaoka, Short coverings in tridimensional spaces arising from sumfree sets, European J. Combin., vol. 29 (2008), 227233. 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), 322326. MR 2565199 (2011e:13049)
 15.
 S.K. Zaremba, A covering theorem for abelian groups, J. London Math. Soc., vol. 26 (1951), 7172. 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}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/S002557182012026135
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.
