Geri Dön

Graph problems in call models and switching networks

Çağrı modelleri ve anahtarlama ağlarında çizge problemleri

  1. Tez No: 517870
  2. Yazar: ABDULLAH ATMACA
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT, PROF. DR. A. YAVUZ ORUÇ
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 84

Özet

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.

Özet (Çeviri)

In the first part of this dissertation, we focus on graph problems that arise in call models. Such models are used to study the combinatorial properties of certain types of calls that include unicast, multicast, and bicast interconnections. Here we focus on bicast calls, and provide closed-form expressions for the number of unlabeled bicast calls when either the number of callers or number of receivers is fixed to 2 or 3. We then obtain lower and upper bounds on the number of such calls by solving an open problem in graph theory, namely counting the number of unlabeled bipartite graphs. Next, these results are extended to left (right) set labeled and set labeled bipartite graphs. In the second part of the dissertation, we focus on wiring and routing problems for one-sided, binary tree switching networks. Specifically, we reduce the O(n) time complexity of the routing algorithm for the one-sided, binary tree switching network to O(lg n). We also present a new wiring algorithm for one-sided, binary tree switching networks. Finally, an algorithm is presented to locate the cluster in which the terminals of the corresponding one-sided binary tree switching network are paired. The time complexity of this algorithm is shown to be O(lg n).

Benzer Tezler

  1. Unified combinatorial interaction testing

    Tümleşik kombinezon etkileşim sınama yöntemi

    HANEFİ MERCAN

    Doktora

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CEMAL YILMAZ

  2. Enriching predictive models using graph embeddings

    Tahminleme modellerinin çizge gömmeleri kullanılarak zenginleştirilmesi

    YAREN YILMAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. ŞULE ÖĞÜDÜCÜ

  3. Kümeleme yöntemleri ile müşteri kanal göçü analizi

    Customer channel migration analysis with clustering methods

    GİZEM ÇALIŞKAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ MEHMET YASİN ULUKUŞ

  4. Runtime race detection for shared memory programming models

    Paylaşımlı bellek programlama modelleri için çalışma zamanı yarışı algılama

    HASSAN SALEHE MATAR

    Doktora

    İngilizce

    İngilizce

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ DİDEM UNAT

  5. Efficient analysis of large-scale social networks using big-data platforms

    Büyük ölçekli sosyal ağların büyük veri platformu kullanarak etkin analizi

    HİDAYET AKSU

    Doktora

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. İBRAHİM KÖRPEOĞLU