Institute of Theoretical Informatics, Algorithmics

Interference Networks

Undisturbed communication

A set of n communication hosts is to be connected via a communication network. The network should be connected but as each signal transmission causes interferences it should not contain many links. We present an algorithm that constructs an interference-minimal network for the following graph types: spanning tree, t-spanner, and d-hop network.

Joint work with Joachim Gudmundsson and Herman Haverkort.

Publications

  1. Marc Benkert, Joachim Gudmundsson, Herman Haverkort, and Alexander Wolff. Constructing interference-minimal networks. In Jiří Wiedermann, Julius Stuller, Gerard Tel, Jaroslav Pokorny, and Mária Bieliková, editors, Proc. 32nd Internat. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM'06), volume 3831 of Lecture Notes in Computer Science, pages 166-175. Springer-Verlag, 2006. [ bib | html | pdf ]
  2. Marc Benkert, Joachim Gudmundsson, Herman Haverkort, and Alexander Wolff. Constructing interference-minimal networks. In Proc. 21st European Workshop on Computational Geometry (EWCG'05), pages 203-206, Eindhoven, 2005. [ bib | pdf ]