Birgit Engels
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Verallgemeinerte minimale Manhattannetzwerke im 3D

Zunächst wird eine verallgemeinerte Version des MMN-Problems, das transitive minimale Manhattansubnetzwerk (TMMSN) vorgestellt. Hier müssen von n gegebenen Punkten (in der Ebene oder im Raum) nur gewisse Punktpaare verbunden werden. Zusätzlich fordern wir die Transitivität der Verbindungsrelation. (Sollen a und b sowie b und c durch einen kürzesten L1-Pfad verbunden werden, so auch a und c.) Damit lässt das NP-Vollständigkeitsresultat des RSMA (Rectilinear Steiner Minimum Arboreszenz) Problems nicht übertragen und es wird ein neuer Reduktionsbeweis für die NP-Schwere des TMMSN-Problems im Raum vorgestellt.