Modern Large-Scale Algorithms for Classical Graph Problems

Simple item page
dc.contributor.advisorHajiaghayi, MohammadTaghien_US
dc.contributor.authorBehnezhad, Soheilen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2021-09-22T05:39:07Z
dc.date.available2021-09-22T05:39:07Z
dc.date.issued2021en_US
dc.description.abstractAlthough computing power has advanced at an astonishing rate, it has been far outpaced by the growing scale of data. This has led to an abundance of algorithmic problems where the input tends to be, by orders of magnitude, larger than the memory available on a single machine. The challenges of data processing at this scale are inherently different from those of traditional algorithms. For instance, without having the whole input properly stored in the memory of a single machine, it is unrealistic to assume that any arbitrary location of the input can be accessed at the same cost; an assumption that is essential for traditional algorithms. In this thesis, we focus on modern computational models that capture these challenges more accurately, and devise new algorithms for several classical graph problems. Specifically, we study models of computation that only allow the algorithm to use sublinear resources (such as time, space, or communication). Examples include (i) massively parallel computation (à la MapReduce) algorithms where the workload is distributed among several machines each with sublinear space/communication, (ii) sublinear-time algorithms that take time sublinear in the input size, (iii) streaming algorithms that take only few passes over the input having access to a sublinear space, and (iv) dynamic algorithms that maintain a property of a dynamically changing input using a sublinear time per update. We propose new algorithms for classical graph problems such as maximum/maximal matching, maximal independent set, minimum vertex cover, and graph connectivity in these models that substantially improve upon the state-of-the-art and are in many cases optimal. Many of our algorithms build on model-independent tools and ideas that are of independent interest and lead to improved bounds in more than one of the aforementioned settings.en_US
dc.identifierhttps://doi.org/10.13016/an98-igjc
dc.identifier.urihttp://hdl.handle.net/1903/27969
dc.language.isoenen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolleddynamic algorithmsen_US
dc.subject.pquncontrolledgraph algorithmsen_US
dc.subject.pquncontrolledlarge-scale algorithmsen_US
dc.subject.pquncontrolledmassively parallel computationen_US
dc.subject.pquncontrolledstreamingen_US
dc.subject.pquncontrolledsublinear time algorithmsen_US
dc.titleModern Large-Scale Algorithms for Classical Graph Problemsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Behnezhad_umd_0117E_21955.pdf
Size:
4.91 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations