Yıl 2019, Cilt 9 , Sayı 2, Sayfalar 374 - 385 2019-12-30

Valid Inequalities for the Maximal Matching Polytope
Maksimal Eşleme Politopu için Geçerli Eşitsizlikler

Mustafa Kemal Tural [1]


    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.


    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.


  • [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.
Birincil Dil en
Konular Matematik
Bölüm Matematik
Yazarlar

Orcid: 0000-0002-7173-7646
Yazar: Mustafa Kemal Tural (Sorumlu Yazar)
Kurum: MIDDLE EAST TECHNICAL UNIVERSITY
Ülke: Turkey


Tarihler

Başvuru Tarihi : 16 Mart 2019
Kabul Tarihi : 18 Aralık 2019
Yayımlanma Tarihi : 30 Aralık 2019

Bibtex @araştırma makalesi { adyujsci540858, journal = {Adıyaman University Journal of Science}, issn = {2147-1630}, eissn = {2146-586X}, address = {}, publisher = {Adıyaman Üniversitesi}, year = {2019}, volume = {9}, pages = {374 - 385}, doi = {10.37094/adyujsci.540858}, title = {Valid Inequalities for the Maximal Matching Polytope}, key = {cite}, author = {Tural, Mustafa Kemal} }
APA Tural, M . (2019). Valid Inequalities for the Maximal Matching Polytope . Adıyaman University Journal of Science , 9 (2) , 374-385 . DOI: 10.37094/adyujsci.540858
MLA Tural, M . "Valid Inequalities for the Maximal Matching Polytope" . Adıyaman University Journal of Science 9 (2019 ): 374-385 <https://dergipark.org.tr/tr/pub/adyujsci/issue/51277/540858>
Chicago Tural, M . "Valid Inequalities for the Maximal Matching Polytope". Adıyaman University Journal of Science 9 (2019 ): 374-385
RIS TY - JOUR T1 - Valid Inequalities for the Maximal Matching Polytope AU - Mustafa Kemal Tural Y1 - 2019 PY - 2019 N1 - doi: 10.37094/adyujsci.540858 DO - 10.37094/adyujsci.540858 T2 - Adıyaman University Journal of Science JF - Journal JO - JOR SP - 374 EP - 385 VL - 9 IS - 2 SN - 2147-1630-2146-586X M3 - doi: 10.37094/adyujsci.540858 UR - https://doi.org/10.37094/adyujsci.540858 Y2 - 2019 ER -
EndNote %0 Adıyaman Üniversitesi Fen Bilimleri Dergisi Valid Inequalities for the Maximal Matching Polytope %A Mustafa Kemal Tural %T Valid Inequalities for the Maximal Matching Polytope %D 2019 %J Adıyaman University Journal of Science %P 2147-1630-2146-586X %V 9 %N 2 %R doi: 10.37094/adyujsci.540858 %U 10.37094/adyujsci.540858
ISNAD Tural, Mustafa Kemal . "Valid Inequalities for the Maximal Matching Polytope". Adıyaman University Journal of Science 9 / 2 (Aralık 2019): 374-385 . https://doi.org/10.37094/adyujsci.540858
AMA Tural M . Valid Inequalities for the Maximal Matching Polytope. ADYU J SCI. 2019; 9(2): 374-385.
Vancouver Tural M . Valid Inequalities for the Maximal Matching Polytope. Adıyaman University Journal of Science. 2019; 9(2): 374-385.
IEEE M. Tural , "Valid Inequalities for the Maximal Matching Polytope", Adıyaman University Journal of Science, c. 9, sayı. 2, ss. 374-385, Ara. 2020, doi:10.37094/adyujsci.540858