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.
Ö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 ↗
Devamı Pofolia uygulamasında
Çıkarımlar, ana noktalar ve makaleye soru sorma; ilgi alanına göre her gün yeni özetler. Ücretsiz.
Web'de giriş yaparak açAlan: Hesaplamalı Kuram ve Matematik
Computational Theory and MathematicsComputer Science