Distributed algorithms for modern communication networks / by Thorsten Götte ; Reviewers: Prof. Dr. Christian Scheideler, Prof. Dr. Sevag Gharibian. Paderborn, 2025
Content
- Introduction
- Contributions & Structure of this Thesis
- Part I: Fast Construction of Overlays and its Applications
- Part II: Distributed Algorithms for Graph Problems
- Preliminaries & Notations
- Basic Terms from Graph Theory
- Restricted Graph Classes
- Basic Terms from Complexity Theory
- Basic Terms from Probability Theory
- Model(s)
- List of Own Publications
- I Fast Overlay Construction and its Applications
- Time-Optimal Construction Of Overlays
- The Overlay Construction Algorithm
- Mathematical Preliminaries for Theorem 1
- Analysis of CreateExpander
- Fast Computation of Connected Components
- Fast Construction of Spanning Forests
- An O(log Delta + loglog n)-Time Algorithm for MIS
- Conclusion to Part I
- II Distributed Graph Algorithms for Distance Based Problems
- Preliminaries for Part II
- A Divide-And-Conquer Theorem for Distributed Algorithms
- The Minor Aggregation Framework
- Approximate Set-Source Shortest Paths in CONGEST and HYBRID
- A Divide-And-Conquer Theorem for Restricted Graphs
- The Tree Operations of Ghaffari and Zuzic
- Weak Separators Via Approximate Distances
- Fast Construction of Separators for Planar Graphs
- Planar Graphs: Embeddings, Faces, and Augmentations
- Fast Separators in CONGEST
- A Small Toolkit for Planar Graphs in CONGEST
- Subroutine 1: Finding and Communicating in Biconnected Components
- Subroutine 2: Making Planar Graphs Biconnected
- Subroutine 3: Computing (Weighted) Path Separators
- Analysis of ComputePathSep
- Main Algorithm Description & Analysis (Proof of Lemma 9.1)
- Fast Separators in the PRAM and the HYBRID Model
- Strong Low-Diameter Decompositions Via Approximate Distances
- Structure of this Chapter
- Pseudo-Padded Decompositions Using Approximate Shortest Paths
- Low-Diameter Clusterings from Pseudo-Padded Decompositions
- Low-Diameter Decompositions for General Graphs
- Low-Diameter Decompositions for k-path Separable Graphs
- Related Work
- Conclusion & Future Work
- Distributed Construction of Compact Routing Schemes
- Structure of this Chapter
- Efficient Computation of Compact Routing Schemes Using Tree Covers
- An Exact Routing Scheme for Trees
- From (Routing on) Trees to (Routing on) Graphs
- Proof of Lemma 11.1
- Tree Covers Using Pseudo-Padded Decompositions
- Tree Covers Using Weak Separators
- Constructing Additive Tree Covers
- Proof of Lemma 11.8
- From Additive Tree Covers To Hierarchical Tree Covers
- Related Work
- Compact Routing Schemes in the Sequential Model
- Compact Routing Schemes in the CONGEST Model
- Compact Routing Schemes in the HYBRID Model
- Conclusion & Future Work
- Approximating Simple Covering Problems Via Beeping Algorithms
- The Beeping Model
- An Efficient SetCover-Algorithm for the Beeping-Model
- Related Work
- Conclusion & Future Work
- Conclusion to Part II
- References