Skip navigation
Please use this identifier to cite or link to this item:
Title: Sublinear Time Algorithms for Graph Problems
Authors: Liu, Sixue
Advisors: Tarjan, Robert
Contributors: Computer Science Department
Keywords: Algorithm
Subjects: Computer science
Issue Date: 2021
Publisher: Princeton, NJ : Princeton University
Abstract: Processing massive graphs is becoming a more-and-more essential task in big-data analysis nowadays. Many graph problems require running time linear in the input size on the traditional RAM model. But linear time is not good enough in many real-life applications. In this thesis, we focus on theoretical analysis of solving fundamental graph problems on practical big-data platforms such as streaming and parallel computation models, with an emphasis on time efficiency and simplicity. In the first part of this thesis, we study the connected components problem in the parallel computation model. Our first result includes several simple parallel algorithms with a state-of-the-art running time, which are significantly easier to implement comparing to the existing ones. Our second result includes simpler algorithms for connected components and spanning forest that are faster than any previous algorithms when the graph has small diameter -- which is usually true in many graphs generated from real-life instances -- albeit in a much weaker computation model. For the second part of this thesis, we study the graph matching problem. We first give a simple algorithm for approximate bipartite matching on streaming and massively parallel computation models that improve upon the existing ones on the number of passes or space usage. Then we present the first semi-streaming algorithm for exact maximum weight bipartite matching that breaks the linear-pass barrier whenever the graph is not super dense. Our approaches not only leverage the combinatorial properties in the graph, but also reformulate the graph problem and use continuous optimization techniques. We hope the new general techniques developed in this thesis can find further applications in algorithm design emerged in big-data analysis.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Liu_princeton_0181D_13753.pdf1.08 MBAdobe PDFView/Download

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