Parallel Batch-Dynamic Graph Algorithms: Coreness Decomposition and Spanners

This thesis contributes to the burgeoning field of batch-dynamic parallel algorithms by presenting parallel batch-dynamic graph algorithms for coreness decomposition and spanners, as well as a number of other related problems. The first class of problems we consider involves approximating coreness decomposition and several closely related concepts, such as (subgraph) density estimation, arboricity estimation, and low out-degree orientations. These are extremely useful structures for organizing graphs based on their density. Our algorithms process any batch of edge insertions and deletions in polylogarithmic depth while using work that is linear in the batch size (up to logarithmic factors), in the worst case. The second class of problems we consider concerns graph spanners. Over the past two to three decades, graph sparsifications that approximately preserve key graph properties have become essential tools in algorithm design. In particular, spanners—reducing the number of edges while approximately preserving pairwise distances—have been widely studied. We present the first such algorithms for computing and maintaining spanners. These algorithms achieve near-optimal amortized runtime—processing each batch in polylogarithmic depth with work nearly linear in the batch size for any number of processors.

Name thesis:degree_name

Master

Department dc:contributor.department

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

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Koo, Jaehyun

Advisor dc:contributor.advisor

• Ghaffari, Mohsen

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/163695

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/163695