Journals / Adıyaman Üniversitesi Fen Bilimleri Dergisi / 2019 / Cilt: 9 - Sayı: 2
Valid Inequalities for the Maximal Matching Polytope
- Pages
- 374–385
- DOI
- —
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) ç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.