Graph problems in call models and switching networks

Bu tezin ilk bölümünde, çağrı modellerinde ortaya çıkan çizge problemlerine odaklanılmaktadır. Bu tür modeller, tekli çağrı, çoklu çağrı ve karşılıklı çoklu çağrı bağlantılarını içeren bazı çağrı tiplerinin kombinatoryel özelliklerini incelemek için kullanılır. Burada, karşılıklı çoklu çağrılara odaklanıyoruz ve arayanların sayısı veya alıcıların sayısı 2 veya 3'e sabitlendiğinde etiketsiz karşılıklı çoklu çağrıların sayısı için kapalı form ifadeleri sağlıyoruz. Bu durumda, çizge teorisinde açık bir problemi çözerek, yani etiketsiz iki parçalı çizgeleri sayarak bu tür çağrıların sayısıyla ilgili alt ve üst sınırlar elde ediyoruz. Daha sonra, bu sonuçlar, sol(sağ) tarafı küme olarak etiketli ve iki tarafı da küme olarak etiketli iki parçalı çizgelere genişletilmektedir. Tezin ikinci bölümünde, tek taraflı, ikili ağaç anahtarlama ağları için bağlama ve yönlendirme problemlerine odaklanıyoruz. özellikle, tek taraflı, ikili ağaç anahtarlama ağları için yönlendirme algoritmasının O(n) hesaplama zamanını O (lg n)'e düşürüyoruz. Tek taraflı, ikili ağaç anahtarlama ağları için yeni bir bağlama algoritması da sunuyoruz. Son olarak, bağlama tasarımı verilen tek taraflı, ikili ağaç anahtarlama ağının terminallerinin eşleştirildiği kümenin yerini belirlemek için bir algoritma sunulmuştur. Bu algoritmanın zaman karmaşıklığının O(lg n) olduğu gösterilmiştir.