· 2014
Seyrek Rastgele Grafikler Üzerinde Yerel Algoritmaların Sınırları
Limits of local algorithms over sparse random graphs
- 109atıf
- 2014yıl
Kısa özet
Grafik özelliklerini yalnızca yerel bilgileri kullanarak hesaplayan yerel algoritmalar, seyrek rastgele d-düzenli grafiklerde maksimum bağımsız kümlere yakın kümeler bulamaz, bu da önceki bir varsayımı çürütmektedir. Elde edebilecekleri en iyi şey, d sonsuza giderken asimptotik olarak maksimum kümenin boyutunun en az 1/2 + 1/(2√2) (yaklaşık 0.853) katı büyüklüğündedir.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- Yerel algoritmalar, küresel grafik özelliklerini hesaplamak için yalnızca yerel bilgileri ve rastgeleliği kullanır.
- Bir varsayım, yerel algoritmaların seyrek rastgele d-düzenli grafiklerde maksimum bağımsız kümlere yakın kümeler bulabileceğini ima ediyordu.
- Bu makale, yerel algoritmaların, d sonsuza giderken asimptotik olarak maksimum kümenin boyutunun en fazla 0.853 katı büyüklüğünde bağımsız kümeler ürettiğini göstermektedir.
- Sonuç, d sonsuza giderken seyrek rastgele d-düzenli grafikler için geçerlidir.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Research over the years has shown that such algorithms can be surprisingly powerful in terms of computing structures like large independent sets in graphs locally. These algorithms have also been implicitly considered in the work on graph limits, where a conjecture due to Hatami, Lovász and Szegedy [17] implied that local algorithms may be able to compute near-maximum independent sets in (sparse) random d-regular graphs. In this paper we refute this conjecture and show that every independent set produced by local algorithms is smaller that the largest one by a multiplicative factor of at least 1/2+1/(2√2) ≈ .853, asymptotically as d → ∞.
Yazarların özeti; kaynağından alınmıştır., 2014 · 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: Ayrık Matematik ve Kombinatorik
Discrete Mathematics and CombinatoricsMathematics