Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/162756
Title: LATENCY, CONDUCTANCE, AND THE ROLE OF CONNECTIVITY IN GRAPH PROBLEMS
Authors: SUMAN SOURAV
ORCID iD:   orcid.org/0000-0001-6923-5762
Keywords: Graph Algorithm, Latency, Leader Election, Information Dissemination, MST Construction, Conductance
Issue Date: 22-Aug-2019
Citation: SUMAN SOURAV (2019-08-22). LATENCY, CONDUCTANCE, AND THE ROLE OF CONNECTIVITY IN GRAPH PROBLEMS. ScholarBank@NUS Repository.
Abstract: In this thesis, we study how the connectivity of the underlying network graph affects a network's performance. We consider various aspects of graph connectivity determined by the structure of the graph and the distribution of latencies over the graph edges. Edge latency represents the time delay in sending a message from one node to another. We study several graph problems namely leader election, information dissemination and minimum weight spanning tree (MST) construction in various different communication models and show that the time and message complexities required to solve these problems do in fact depend on the connectivity of the given graph as well as the distribution of latencies over the edges of the network or a combination of both.
URI: https://scholarbank.nus.edu.sg/handle/10635/162756
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
SouravS.pdf7.15 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

18
checked on Jan 16, 2020

Download(s)

10
checked on Jan 16, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.