https://dspace.mit.edu/handle/1721.1/109000

MIT Libraries homeMIT Libraries logoDSpace@MIT

MIT
View Item 

  * DSpace@MIT Home
  * MIT Libraries
  * MIT Theses
  * Theses - Dept. of Electrical Engineering and Computer Sciences
  * Electrical Engineering and Computer Sciences - Ph.D. / Sc.D.
  * View Item

  * DSpace@MIT Home
  * MIT Libraries
  * MIT Theses
  * Theses - Dept. of Electrical Engineering and Computer Sciences
  * Electrical Engineering and Computer Sciences - Ph.D. / Sc.D.
  * View Item

JavaScript is disabled for your browser. Some features of this site
may not work without it.
Toggle navigation

Improved distributed algorithms for fundamental graph problems

Author(s)

Ghaffari, Mohsen
Thumbnail
DownloadFull printable version (28.78Mb)

Other Contributors

Massachusetts Institute of Technology. Department of Electrical
Engineering and Computer Science.

Advisor

Nancy Lynch.

Terms of use

MIT theses are protected by copyright. They may be viewed,
downloaded, or printed from this source but further reproduction or
distribution in any format is prohibited without written permission.
http://dspace.mit.edu/handle/1721.1/7582

Metadata

Show full item record

Abstract

Distributed graph algorithms provide efficient and theoretically
sound methods for solving graph problems in distributed settings and
more generally for performing distributed computation in networks.
These algorithms are applicable in a wide variety of settings,
ranging from computer networks to massively parallel computing and
beyond. This thesis addresses a number of the central problems of
distributed graph algorithms. These problems generally revolve around
two of the principal challenges of the area, locality and congestion.
The problems include computing maximal independent set, minimum
spanning tree, minimum edge cut and minimum vertex cut, graph
connectivity decompositions, network information dissemination,
minimum-weight connected dominating set, and scheduling distributed
protocols. We develop novel techniques, concepts, and tools for these
problems, and present algorithms and impossibility results which
improve considerably on the state of the art, in several cases
resolving or advancing long-standing open problems.

Description

Thesis: Ph. D., Massachusetts Institute of Technology, Department of
Electrical Engineering and Computer Science, 2017.
 
Cataloged from PDF version of thesis.
 
Includes bibliographical references (pages 237-255).
 

Date issued

2017

URI

http://hdl.handle.net/1721.1/109000

Department

Massachusetts Institute of Technology. Department of Electrical
Engineering and Computer Science.

Publisher

Massachusetts Institute of Technology

Keywords

Electrical Engineering and Computer Science.
---------------------------------------------------------------------

Collections

  * Electrical Engineering and Computer Sciences - Ph.D. / Sc.D.
  * Electrical Engineering and Computer Sciences - Ph.D. / Sc.D.

Show Statistical Information

[                    ]
(*)Search DSpace
( )This Collection
Browse

All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitles
SubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

Login

Statistics

OA StatisticsStatistics by CountryStatistics by Department
MIT Libraries homeMIT Libraries logo

Find us on

Twitter Facebook Instagram YouTube RSS

MIT Libraries navigation

SearchHours & locationsBorrow & requestResearch supportAbout us
PrivacyPermissionsAccessibility
MIT
Massachusetts Institute of Technology
Content created by the MIT Libraries, CC BY-NC unless otherwise
noted. Notify us about copyright concerns.