Institut für Theoretische Informatik, Algorithmik

Interferenz-Netzwerke

Störungsfreie Kommunikation

Zwischen n Teilnehmern soll ein Kommunikationsnetzwerk eingerichtet werden. Das Netzwerk soll zusammenhängend sein, aber nicht alle Kanten enthalten, da ein Sendevorgang störende Interferenzen verursacht. Wir geben einen Algorithmus an, der ein interferenz-minimales Netzwerk für die Graphtypen Spannbaum, t-Spanner, und Durchmesser-d-Netzwerke berechnet.

In Zusammenarbeit mit Joachim Gudmundsson und Herman Haverkort.

Publikationen

  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 ]