Improved distributed algorithms for fundamental graph problems
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/109000 |
| _version_ | 1811072635298119680 |
|---|---|
| author | Ghaffari, Mohsen |
| author2 | Nancy Lynch. |
| author_facet | Nancy Lynch. Ghaffari, Mohsen |
| author_sort | Ghaffari, Mohsen |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017. |
| first_indexed | 2024-09-23T09:09:08Z |
| format | Thesis |
| id | mit-1721.1/109000 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:09:08Z |
| publishDate | 2017 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1090002019-04-10T21:03:25Z Improved distributed algorithms for fundamental graph problems Ghaffari, Mohsen Nancy Lynch. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. 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). 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. by Mohsen Ghaffari. Ph. D. 2017-05-11T19:59:57Z 2017-05-11T19:59:57Z 2017 2017 Thesis http://hdl.handle.net/1721.1/109000 986529111 eng 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 255 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Ghaffari, Mohsen Improved distributed algorithms for fundamental graph problems |
| title | Improved distributed algorithms for fundamental graph problems |
| title_full | Improved distributed algorithms for fundamental graph problems |
| title_fullStr | Improved distributed algorithms for fundamental graph problems |
| title_full_unstemmed | Improved distributed algorithms for fundamental graph problems |
| title_short | Improved distributed algorithms for fundamental graph problems |
| title_sort | improved distributed algorithms for fundamental graph problems |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/109000 |
| work_keys_str_mv | AT ghaffarimohsen improveddistributedalgorithmsforfundamentalgraphproblems |