Yayıncı/abone sistemleri Üst-Ağ Tasarımı

Bilgisayarların ilgili oldukları farklı konulara abone olabildikleri yayıncı/abone sistemleri için üst-ağ tasarımı önemli bir problemdir. Yayıncı/abone sisteminin ölçeklenebilir ve verimli olabilmesi için düğümlerin derecelerinin düşük olması önemlidir. Problemi şu şekilde ifade edebiliriz: Düğüm kümesi ve bunların konu abonelikleri verildiğinde, düğümleri birleştirerek en az maksimum dereceli ve konu birleşik bir çizge oluşturunuz. Bu problem için ilk polinom zamanlı yaklaşım algoritmasını tasarladık ve yaklaşım için bir alt sınır ispatladık. Deney sonuçlarımız algoritmamızın yayıncı/abone sistemi maksimum derecesini geliştirdiğini göstermektedir. Bu problemin bir başka çeşitini de önerdik. Bu problemde her konu birleşik ağ sabit çaplı olmak zorundadır ve ortalama derece en az olmak zorundadır. Bu soru için önerdiğimiz algoritma çapın 2 olmasını sağlamaktadır. Deney sonuçları algoritmamızın ortalama dereceyi çok artırmadan, çok düşük bir çap sağladığını göstermektedir.