Abshoff, Sebastian: On the complexity of fundamental problems in dynamic ad-hoc networks. 2015
Inhalt
- List of Definitions and Theorems
- List of Figures
- List of Algorithms
- Preface
- Introduction
- Preliminaries
- Notation
- The Dynamic Network Model
- Fundamental Problems
- Existing Results
- The Algorithm by Kuhn, Lynch, and Oshman
- Lower Bounds for Token-Forwarding Algorithms
- Randomized Network Coding Algorithms
- Related Work
- Geometric Dynamic Networks
- The Geometric Dynamic Network Model
- Related Work
- Upper Bounds for Token-Forwarding Algorithms
- Lower Bounds for Token-Forwarding Algorithms
- Conclusion and Unanswered Questions
- Counting versus Token Dissemination
- Models & Problems
- Related Work
- Same Predecessors & Counting
- Set Equality & Same Predecessors
- Two-Party Communication & Set Equality
- Two-Party Token Dissemination & Set Equality
- Two-Party Token Dissemination & Counting
- Conclusion and Unanswered Questions
- Continuous Aggregation in Dynamic Networks
- Models & Problems
- Related Work
- Static Networks
- T-Stable Dynamic Networks
- Graph Patching Technique
- Noncontinuous Extremum
- Noncontinuous Summation
- Continuous Extremum
- Continuous Summation
- Geometric Dynamic Networks
- Conclusion and Unanswered Questions
- Conclusion & Outlook
- Bibliography