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

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