SavedAdd your journal

Journals / Adıyaman Üniversitesi Fen Bilimleri Dergisi / 2019 / Cilt: 9 Sayı: 2

Valid Inequalities for the Maximal Matching Polytope

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

Mustafa Kemal Tural(MIDDLE EAST TECHNICAL UNIVERSITY)0000-0002-7173-7646
Pages
374–385
Publication Date
2019-12-30
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

In this paper, we introduce new classes of valid inequalities for the maximal matching polytope.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Given a graph G=(V,E), a subset M of E is called a matching if no two edges in M are adjacent.
📊
Key Findings & Data:A matching is said to be maximal if it is not a proper subset of any other matching.
💡
Conclusion & Impact:In this paper, we introduce new classes of valid inequalities for the maximal matching polytope.
🔬Design:Araştırma Makalesi
📍Scope:Comprehensive Sample
⚙️Variables:Eşleme · Maksimal Eşleme · Geçerli eşitsizlikler

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.

Özet

Verilen bir G=(V,E) çiz gesinde, 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.

🔖

Cite This Article

Tural, M. K. (2019). Valid Inequalities for the Maximal Matching Polytope. Adıyaman Üniversitesi Fen Bilimleri Dergisi, Cilt: 9 Sayı: 2, 374–385. https://doi.org/10.37094/adyujsci.540858

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (14)

  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.