Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/162756
DC Field | Value | |
---|---|---|
dc.title | LATENCY, CONDUCTANCE, AND THE ROLE OF CONNECTIVITY IN GRAPH PROBLEMS | |
dc.contributor.author | SUMAN SOURAV | |
dc.date.accessioned | 2019-12-12T18:02:41Z | |
dc.date.available | 2019-12-12T18:02:41Z | |
dc.date.issued | 2019-08-22 | |
dc.identifier.citation | SUMAN SOURAV (2019-08-22). LATENCY, CONDUCTANCE, AND THE ROLE OF CONNECTIVITY IN GRAPH PROBLEMS. ScholarBank@NUS Repository. | |
dc.identifier.uri | https://scholarbank.nus.edu.sg/handle/10635/162756 | |
dc.description.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. | |
dc.language.iso | en | |
dc.subject | Graph Algorithm, Latency, Leader Election, Information Dissemination, MST Construction, Conductance | |
dc.type | Thesis | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.contributor.supervisor | SETH LEWIS GILBERT | |
dc.description.degree | Ph.D | |
dc.description.degreeconferred | DOCTOR OF PHILOSOPHY | |
dc.identifier.orcid | 0000-0001-6923-5762 | |
Appears in Collections: | Ph.D Theses (Open) |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
SouravS.pdf | 7.15 MB | Adobe PDF | OPEN | None | View/Download |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.