Valid Inequalities for the Maximal Matching Polytope

Öz

    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.

Anahtar Kelimeler

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

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

Öz

    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.

Anahtar Kelimeler

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

Kaynakça

1. [1] Budinich, M., Exact bounds on the order of the maximum clique of a graph, Discrete Applied Mathematics, 127(3), 535-543, 2003.
2. [2] Grötschel, M., Wakabayashi, Y., Facets of the clique partitioning polytope, Mathematical Programming, 47(1-3), 367-387, 1990.
3. [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. [4] Yannakakis, M., Gavril, F., Edge dominating sets in graphs, SIAM Journal of Applied Mathematics, 38, 364-372, 1980.
5. [5] Schrijver, A., Combinatorial Optimization - Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24, Springer-Verlag, Berlin, 2003.
6. [6] Horton, J.D., Kilakos, K., Minimum edge dominating sets, SIAM Journal on Discrete Mathematics, 6(3), 375-387, 1993.
7. [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. [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. [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. [10] Hwang, S.F., Chang, G.J., The edge domination problem, Discussiones Mathematicae Graph Theory, 15(1), 51–57, 1995.
11. [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. [12] Chlebík, M., Chlebíková, J., Approximation hardness of edge dominating set problems, Journal of Combinatorial Optimization, 11(3), 279–290, 2006.
13. [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. [14] Tural, M.K., Maximal matching polytope in trees, Optimization Methods and Software, 31(3), 471-478, 2016.