Models and algorithms for hybrid networks and hybrid programmable matter / Kristian Hinnenthal ; [Reviewers: Christian Scheideler, Paderborn University, Friedhelm Meyer auf der Heide, Paderborn University, Irina Kostitsyna, Eindhoven University of Technology]. Paderborn, 2021
Inhalt
- Introduction
- Hybrid Networks
- Prologue
- Fast Construction of Overlay Networks
- Algorithmic Primitives
- Transforming G into a Sparse Graph
- High-Level Algorithm
- A Single Subphase
- Conclusion of the Algorithm
- Outlook
- Distributed Computation with Node Capacities
- Algorithmic Primitives
- Minimum Spanning Tree
- Computing an O(a)-Orientation
- Further Graph Problems
- Breadth-First Search Trees
- Single-Source Shortest Paths
- Maximal Independent Set
- Maximal Matching
- O(a)-Coloring
- Outlook
- Shortest Paths in Sparse Hybrid Networks
- Path Graphs
- Cycle Graphs
- Trees
- Pseudotrees
- Cactus Graphs
- Sparse Graphs
- Hierarchical Tree Decomposition
- Finding Nearest Shortcut Nodes
- Computing APSP between Shortcut Nodes
- Approximating SSSP and the Diameter
- Outlook
- Shortest Paths in General Hybrid Networks
- Hybrid Programmable Matter
- Shape Formation in Hybrid Programmable Matter
- Finding Safely Removable Tiles
- Forming an Intermediate Structure
- Forming a Triangle
- Towards Multiple Robots
- Outlook
- Shape Recognition in Hybrid Programmable Matter
- Recognizing Simple Shapes
- Recognizing Parallelograms with Specific Side Ratio
- A Robot without any Pebble
- A Robot with a Single Pebble
- A Robot With Two Pebbles
- A Family of Functions Requiring an Increasing Amount of Pebbles
- Outlook
- Bibliography