ACM Transactions on Algorithms· 2026Q1
Uzun pençeler içermeyen seyrek graflarda Maksimum Ağırlıklı Bağımsız Küme
Max Weight Independent Set in sparse graphs with no long claws
- 1atıf
- Q1SCImago
- 2026yıl
Kısa özet
Belirli yapıları dışlayan graflarda Maksimum Ağırlıklı Bağımsız Küme (MWIS) problemi için polinom zamanlı bir algoritma sunulmuştur: yollar ve alt bölümlenmiş pençelerden oluşan sabit bir orman ve ayrıca bir alt graf olarak sabit bir biklik.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- Maksimum Ağırlıklı Bağımsız Küme (MWIS) problemi için polinom zamanlı bir algoritma sunulmaktadır.
- Algoritma, belirli indüklenmiş alt grafları dışlayan graflara uygulanır: yollar ve alt bölümlenmiş pençelerden oluşan sabit bir orman.
- Algoritma ayrıca bir alt graf olarak sabit bir biklikin dışlanmasını da gerektirir.
- Bu, MWIS'in kısıtlı graf sınıflarındaki karmaşıklığını belirlemeyle ilgili önemli açık bir problemi ele almaktadır.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
For graphs \(G\) and \(H\) , we say that \(G\) is \(H\) -free if it does not contain \(H\) as an induced subgraph. Already in the early 1980s Alekseev observed that the Max Weight Independent Set problem ( MWIS ) remains NP -hard in \(H\) -free graphs, unless every component of \(H\) is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then, determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. In this paper we make an important step towards solving the problem by providing a polynomial-time algorithm for MWIS in graphs excluding a fixed graph forest of paths and subdivided claws as an induced subgraph, and a fixed biclique as a subgraph.
Yazarların özeti; kaynağından alınmıştır. ACM Transactions on Algorithms, 2026 · DOI ↗
Ücretsiz hesapla devam et
Makaleye Sor ile bu makaleye günde 3 soru ücretsiz; makaleyi kaydet, kaynakçasını al, ilgi alanına göre her gün yeni özetler. Çıkarımlar Premium.
Web'de ücretsiz devam etGoogle ya da Apple hesabınla giriş; kart istemez. Bu makaleye geri dönersin.
Telefonda:
Alan: Hesaplamalı Kuram ve Matematik
Computational Theory and MathematicsComputer Science