KaydedilenlerDerginizi ekleyin

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

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

Valid Inequalities for the Maximal Matching Polytope

Mustafa Kemal Tural(MIDDLE EAST TECHNICAL UNIVERSITY)0000-0002-7173-7646
Sayfa
374–385
Yayın Tarihi
2019-12-30
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

Bu çalışmada, maksimal eşleme politopu için yeni geçerli eşitsizlik sınıfları sunulmaktadır.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:Verilen bir G=(V,E) çiz gesinde, uçları kesişmeyen kenarlardan oluşan M k ümesine eşleme denir.
📊
Temel Bulgular & Veri:Herhangi başka bir eşlemenin öz altkümesi olmayan bir eşlemeye maksimal eşleme denir.
💡
Sonuç & Katkı:Bu çalışmada, maksimal eşleme politopu için yeni geçerli eşitsizlik sınıfları sunulmaktadır.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Eşleme · Maksimal Eşleme · Geçerli eşitsizlikler

Ö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.

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.

🔖

Bu Makaleye Atıf Yap

Tural, M. K. (2019). Maksimal Eşleme Politopu için Geçerli Eşitsizlikler. Adıyaman Üniversitesi Fen Bilimleri Dergisi, Cilt: 9 Sayı: 2, 374–385. https://doi.org/10.37094/adyujsci.540858

📄 Tam Metin PDF Okuyucu

📄

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

Kaynakça (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.