Valid Inequalities for the Maximal Matching Polytope

Year 2019, Volume: 9 Issue: 2, 374 - 385, 30.12.2019

Mustafa Kemal Tural

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.

Keywords

Matching, Maximal matching, Valid inequalities, Matching polytope, Maximal matching polytope

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

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.

Keywords

Eşleme, Maksimal Eşleme, Geçerli eşitsizlikler, Eşleme politopu, Maksimal eşleme politopu

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.