Algorithms for Sensor Systems. 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014 Wroclaw, Poland, September 12, 2014 Revised Selected Papers

Description

Preface Organization Algorithmic Challenges in M2M (Invited Talk) Contents Robot Planning The Multi-source Beachcombers' Problem 1 Introduction 1.1 Preliminaries and Notation 1.2 Outline and Results of the Paper 1.3 Related Work 2 t-SBP as a Partitioning Problem and its Hardness 2.1 A Deterministic Approximation Guarantee for 2-SBP 2.2 An Exact Solution for t-SBP with S-Uniform Swarms 3 A Randomized Algorithm for t-SBP 4 Conclusion and Open Problems References Multi-Robot Foremost Coverage of Time-Varying Graphs 1 Introduction 1.1 Related Results 1.2 Main Results 2 k-Agent Border Coverage in R 3 Two Agents on a Tree 4 Conclusion and Discussion References Strategies for Parallel Unaware Cleaners 1 Introduction 2 Model 3 Simple Cleaning Examples 4 Canonical Cleaning and General Observations 5 The Torus and the Grid Graph 6 Unaware Parallel Traversal of General Graphs 7 Conclusion A Appendix A.1 Canonical Cleaning A.2 Canonical Algorithm First Visit A.3 Analysis of Torus Algorithm A.4 Proof of Lemma 3 A.5 Analysis of Algorithm 5 References Minimum-Traveled-Distance Gathering of Oblivious Robots over Given Meeting Points 1 Introduction 2 Definitions 3 Basic Results 4 Exact Gathering 4.1 Classes S1, S2, and S3 4.2 Class S4: All Robots and Weber Points on a Line 4.3 Class S5: Rotations 4.4 Class S6: Reflections with Robots and Weber Points on the Axis 4.5 Class S7: Reflections with Robots but No Weber Points on the Axis 4.6 Class S8: Reflections with Weber Points but No Robots on the Axis 4.7 Class S9: Asymmetric 5 Conclusion References Algorithms and Data Structures on Graphs Fast Rendezvous with Advice 1 Introduction 1.1 Background 1.2 Model and Problem Description 1.3 Our Results 1.4 Related Work 2 The Advice and the Algorithm 3 The Lower Bound 4 Conclusion References Computing the Dynamic Diameter of Non-Deterministic Dynamic Networks is Hard 1 Introduction 2 Notations and Definitions 3 The Dynamic Diameter Problem is Not in APX for Undirected Networks 4 The Dynamic Diameter Problem is NP-Complete Even for Statically Connected Networks 5 The Dynamic Diameter Problem is Not in APX for Statically Strongly Connected Networks 6 Conclusion and Future Works References Improved Spanners in Networks with Symmetric Directional Antennas 1 Introduction 1.1 Related Work 1.2 Our Results 1.3 Preliminaries and Notation 2 5-Gadgets and their Properties 2.1 Outline 2.2 5-Gadgets 3 7-Spanner 4 Stretch Factor 5 5 Conclusions References Wireless Networks Exploiting Geometry in the SINRk Model 1 Introduction 2 Maximum Capacity 2.1 An O(1)-Approximation for Constant k 2.2 All Pairs Maximum Capacity 3 Scheduling 4 A PTAS for Maximum Capacity with k=1 References Interference Minimization in Asymmetric Sensor Networks 1 Introduction 2 Preliminaries and Notation 3 NP-completeness in Two Dimensions 4 The One-Dimensional Case 4.1 Properties of Optimal Solutions 4.2 A Quasi-Polynomial Algorithm 5 Further Structural Properties in One Dimension 5.1 Nearest Neighbor Algorithm and Lower Bound 5.2 Bends 6 Conclusion References Minimum Latency Aggregation Scheduling in Wireless Sensor Networks 1 Introduction 1.1 Related Work 1.2 Our Results 1.3 Model and Problem Statement 2 Unit Interval Graphs 3 Optimal Algorithm for Regular Unit Interval Graphs 4 Optimal Convergecast for Grids and Tori References Author Index