Research Article
BibTex RIS Cite

Valid Inequalities for the Maximal Matching Polytope

Year 2019, Volume: 9 Issue: 2, 374 - 385, 30.12.2019
https://doi.org/10.37094/adyujsci.540858

Abstract



    Given a graph G=(V,E),






a subset M of E is called a matching
if no two edges in M
 are adjacent. A
matching is said to be maximal if it is not a proper subset of any other
matching. The maximal matching polytope associated with graph G
is the convex hull of
the incidence vectors of maximal matchings in G
. In this paper, we introduce new classes of valid
inequalities for the maximal matching polytope.




References

  • [1] Budinich, M., Exact bounds on the order of the maximum clique of a graph, Discrete Applied Mathematics, 127(3), 535-543, 2003.
  • [2] Grötschel, M., Wakabayashi, Y., Facets of the clique partitioning polytope, Mathematical Programming, 47(1-3), 367-387, 1990.
  • [3] Taşkın, Z.C., Ekim, T., Integer programming formulations for the minimum weighted maximal matching problem, Optimization Letters, 6, 1161-1171, 2012.
  • [4] Yannakakis, M., Gavril, F., Edge dominating sets in graphs, SIAM Journal of Applied Mathematics, 38, 364-372, 1980.
  • [5] Schrijver, A., Combinatorial Optimization - Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24, Springer-Verlag, Berlin, 2003.
  • [6] Horton, J.D., Kilakos, K., Minimum edge dominating sets, SIAM Journal on Discrete Mathematics, 6(3), 375-387, 1993.
  • [7] Demange, M., Ekim, T., Minimum Maximal Matching is NP-Hard in Regular Bipartite Graphs, in Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 4978, 364-374, Springer, Berlin, 2008.
  • [8] Mitchell, S., Hedetniemi, S.T., Edge domination in trees, in: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, Louisiana State University, Baton Rouge, 19, 489–509, 1977.
  • [9] Richey, M.B., Parker, R.G., Minimum-maximal matching in series-parallel graphs, European Journal of Operational Research, 33(1), 98–105, 1988.
  • [10] Hwang, S.F., Chang, G.J., The edge domination problem, Discussiones Mathematicae Graph Theory, 15(1), 51–57, 1995.
  • [11] Cardinal, J., Langerman, S., Levy, E., Improved approximation bounds for edge dominating set in dense graphs, Theoretical Computer Science, 410, 949–957, 2009.
  • [12] Chlebík, M., Chlebíková, J., Approximation hardness of edge dominating set problems, Journal of Combinatorial Optimization, 11(3), 279–290, 2006.
  • [13] Bodur, M., Ekim, T., Taşkın, Z.C., Decomposition algorithms for solving the minimum weight maximal matching problem, Networks, 62, 273–287, 2013.
  • [14] Tural, M.K., Maximal matching polytope in trees, Optimization Methods and Software, 31(3), 471-478, 2016.

Maksimal Eşleme Politopu için Geçerli Eşitsizlikler

Year 2019, Volume: 9 Issue: 2, 374 - 385, 30.12.2019
https://doi.org/10.37094/adyujsci.540858

Abstract


    Verilen bir G=(V,E) çizgesinde, uçları
kesişmeyen kenarlardan oluşan M k
ümesine eşleme denir.
Herhangi başka bir eşlemenin öz altkümesi olmayan bir eşlemeye maksimal eşleme
denir. G çizgesindeki maksimal eşlemelerin insidans vektörlerinin konveks
örtüsüne G kümesi ile ilişkili maksimal eşleme politopu adı verilir. Bu çalışmada,
maksimal eşleme politopu için yeni geçerli eşitsizlik sınıfları sunulmaktadır.




References

  • [1] Budinich, M., Exact bounds on the order of the maximum clique of a graph, Discrete Applied Mathematics, 127(3), 535-543, 2003.
  • [2] Grötschel, M., Wakabayashi, Y., Facets of the clique partitioning polytope, Mathematical Programming, 47(1-3), 367-387, 1990.
  • [3] Taşkın, Z.C., Ekim, T., Integer programming formulations for the minimum weighted maximal matching problem, Optimization Letters, 6, 1161-1171, 2012.
  • [4] Yannakakis, M., Gavril, F., Edge dominating sets in graphs, SIAM Journal of Applied Mathematics, 38, 364-372, 1980.
  • [5] Schrijver, A., Combinatorial Optimization - Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24, Springer-Verlag, Berlin, 2003.
  • [6] Horton, J.D., Kilakos, K., Minimum edge dominating sets, SIAM Journal on Discrete Mathematics, 6(3), 375-387, 1993.
  • [7] Demange, M., Ekim, T., Minimum Maximal Matching is NP-Hard in Regular Bipartite Graphs, in Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 4978, 364-374, Springer, Berlin, 2008.
  • [8] Mitchell, S., Hedetniemi, S.T., Edge domination in trees, in: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, Louisiana State University, Baton Rouge, 19, 489–509, 1977.
  • [9] Richey, M.B., Parker, R.G., Minimum-maximal matching in series-parallel graphs, European Journal of Operational Research, 33(1), 98–105, 1988.
  • [10] Hwang, S.F., Chang, G.J., The edge domination problem, Discussiones Mathematicae Graph Theory, 15(1), 51–57, 1995.
  • [11] Cardinal, J., Langerman, S., Levy, E., Improved approximation bounds for edge dominating set in dense graphs, Theoretical Computer Science, 410, 949–957, 2009.
  • [12] Chlebík, M., Chlebíková, J., Approximation hardness of edge dominating set problems, Journal of Combinatorial Optimization, 11(3), 279–290, 2006.
  • [13] Bodur, M., Ekim, T., Taşkın, Z.C., Decomposition algorithms for solving the minimum weight maximal matching problem, Networks, 62, 273–287, 2013.
  • [14] Tural, M.K., Maximal matching polytope in trees, Optimization Methods and Software, 31(3), 471-478, 2016.
There are 14 citations in total.

Details

Primary Language English
Subjects Mathematical Sciences
Journal Section Mathematics
Authors

Mustafa Kemal Tural 0000-0002-7173-7646

Publication Date December 30, 2019
Submission Date March 16, 2019
Acceptance Date December 18, 2019
Published in Issue Year 2019 Volume: 9 Issue: 2

Cite

APA Tural, M. K. (2019). Valid Inequalities for the Maximal Matching Polytope. Adıyaman University Journal of Science, 9(2), 374-385. https://doi.org/10.37094/adyujsci.540858
AMA Tural MK. Valid Inequalities for the Maximal Matching Polytope. ADYU J SCI. December 2019;9(2):374-385. doi:10.37094/adyujsci.540858
Chicago Tural, Mustafa Kemal. “Valid Inequalities for the Maximal Matching Polytope”. Adıyaman University Journal of Science 9, no. 2 (December 2019): 374-85. https://doi.org/10.37094/adyujsci.540858.
EndNote Tural MK (December 1, 2019) Valid Inequalities for the Maximal Matching Polytope. Adıyaman University Journal of Science 9 2 374–385.
IEEE M. K. Tural, “Valid Inequalities for the Maximal Matching Polytope”, ADYU J SCI, vol. 9, no. 2, pp. 374–385, 2019, doi: 10.37094/adyujsci.540858.
ISNAD Tural, Mustafa Kemal. “Valid Inequalities for the Maximal Matching Polytope”. Adıyaman University Journal of Science 9/2 (December 2019), 374-385. https://doi.org/10.37094/adyujsci.540858.
JAMA Tural MK. Valid Inequalities for the Maximal Matching Polytope. ADYU J SCI. 2019;9:374–385.
MLA Tural, Mustafa Kemal. “Valid Inequalities for the Maximal Matching Polytope”. Adıyaman University Journal of Science, vol. 9, no. 2, 2019, pp. 374-85, doi:10.37094/adyujsci.540858.
Vancouver Tural MK. Valid Inequalities for the Maximal Matching Polytope. ADYU J SCI. 2019;9(2):374-85.

...