The transitive minimum Manhattan subnetwork problem in 3 dimensions. (English) Zbl 1226.05098
Summary: We consider the Minimum Manhattan Subnetwork (MMSN) Problem which generalizes the already known Minimum Manhattan Network (MMN) Problem: Given a set \(P\) of \(n\) points in the plane, find shortest rectilinear paths between all pairs of points. These paths form a network, the total length of which has to be minimized. From a graph theoretical point of view, a MMN is a 1-spanner with respect to the \(L_{1}\) metric. In contrast to the MMN problem, a solution to the MMSN problem does not demand \(L_{1}\)-shortest paths for all point pairs, but only for a given set \(R \subseteq P \times P\) of pairs. The complexity status of the MMN problem is still unsolved in \(\geq 2\) dimensions, whereas the MMSN was shown to be \(N\)P-complete considering general relations \(R\) in the plane. We restrict the MMSN problem to transitive relations \(R_T\) (Transitive Minimum Manhattan Subnetwork (TMMSN) Problem) and show that the TMMSN problem in 3 dimensions is \(NP\)-complete.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68M10 | Network design and communication in computer systems |
References:
| [1] | Benkert, M.; Widmann, F.; Wolff, A., The minimum Manhattan network problem: Approximations and exact solutions, Computational Geometry: Theory and Applications, 35, 3, 188-208 (2006) · Zbl 1144.90319 |
| [2] | Chepoi, V.; Nouioua, K.; Vaxes, Y., A rounding algorithm for approximating minimum Manhattan networks, Theoretical Computer Science, 390, 1, 56-69 (2008) · Zbl 1209.90069 |
| [3] | B. Fuchs, A. Schulze, A simple 3-approximation of minimum Manhattan networks, Technical Report zaik2008-570, ZAIK, University of Cologne, 2008; B. Fuchs, A. Schulze, A simple 3-approximation of minimum Manhattan networks, Technical Report zaik2008-570, ZAIK, University of Cologne, 2008 |
| [4] | Garey, M. R.; Johnson, D. S., The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, 32, 826-834 (1977) · Zbl 0396.05009 |
| [5] | Gudmundsson, J.; Levcopoulos, C.; Narasimhan, G., Approximating a minimum Manhattan network, Nordic Journal of Computing, 8, 2, 219-232 (2001) · Zbl 0985.68092 |
| [6] | Kato, R.; Imai, K.; Asano, T., An improved algorithm for the minimum Manhattan network problem, (Proceedings of the 13th International Symposium on Algorithms and Computations. Proceedings of the 13th International Symposium on Algorithms and Computations, ISAAC 2002. Proceedings of the 13th International Symposium on Algorithms and Computations. Proceedings of the 13th International Symposium on Algorithms and Computations, ISAAC 2002, Lecture Notes in Computer Science, vol. 2518 (2002), Springer), 344-356 · Zbl 1019.68819 |
| [7] | M. Koehler, Diplomarbeit: Berechnung minimaler Manhattan Netzwerke, University of Bonn, 2006; M. Koehler, Diplomarbeit: Berechnung minimaler Manhattan Netzwerke, University of Bonn, 2006 |
| [8] | Lam, F.; Alexandersson, M.; Pachter, L., Picking alignments from (Steiner) trees, Journal of Computational Biology, 10, 3-4, 509-520 (2003) |
| [9] | K. Nouioua, Thèse de Doctorat en Informatique: Enveloppes de Pareto et Réseaux de Manhattan: charactéresations et algorithmes, Université de la Mediterranée, 2005; K. Nouioua, Thèse de Doctorat en Informatique: Enveloppes de Pareto et Réseaux de Manhattan: charactéresations et algorithmes, Université de la Mediterranée, 2005 |
| [10] | K. Nouioua, Une approche primale-duale pour le problme du reseau de Manhattan minimal, RAIRO Operations Research (submitted for publication); K. Nouioua, Une approche primale-duale pour le problme du reseau de Manhattan minimal, RAIRO Operations Research (submitted for publication) |
| [11] | Papadimitriou, C.; Yannakakis, M., Optimization, approximation and complexity classes, Journal of Computer and System Sciences, 43, 425-440 (1991) · Zbl 0765.68036 |
| [12] | W. Shi, C. Su, The rectilinear Steiner arborescence problem is NP-complete, in: Symposium on Discrete Algorithms, 2000, pp. 780-787; W. Shi, C. Su, The rectilinear Steiner arborescence problem is NP-complete, in: Symposium on Discrete Algorithms, 2000, pp. 780-787 · Zbl 0957.68085 |
| [13] | Seibert, S.; Unger, W., A 1.5-approximation of the minimal Manhattan network problem, (Proceedings 16th International Symposium on Algorithms and Computation. Proceedings 16th International Symposium on Algorithms and Computation, ISAAC 2005. Proceedings 16th International Symposium on Algorithms and Computation. Proceedings 16th International Symposium on Algorithms and Computation, ISAAC 2005, Lecture Notes in Computer Science, vol. 3827 (2005), Springer), 246-255 · Zbl 1173.68869 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
