Local Algorithms for Sparsification of Average-case Graphs
Given an input graph 𝐺, a Local Computation Algorithm for sparse spanning graphs provides query access to a sparse subgraph 𝐺′ ⊆ 𝐺, where 𝐺′ maintains the connectivity and/or distances in 𝐺, by making a sublinear number of probes to the input 𝐺 for each query to 𝐺′ . It is known that worst-case grap...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144952 |