Universität zu Köln
Mathematisch-Naturwissenschaftliche Fakultät
Arbeitsgruppe Faigle/Schrader
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.
© Arbeitsgruppe Faigle/Schrader, letzte Änderung: 15.11.2007