Back to Search
Start Over
Computational complexity of the 2-connected Steiner network problem in the ℓp plane.
- Source :
-
Theoretical Computer Science . Jan2021, Vol. 850, p168-184. 17p. - Publication Year :
- 2021
-
Abstract
- The geometric 2-connected Steiner network problem asks for a shortest bridgeless network spanning a given set of terminals in the plane such that the total length of all edges of the network, as measured in the ℓ p metric, is a minimum. Using reduction from the problem of deciding the Hamiltonicity of planar cubic bipartite graphs we show that this problem is NP-hard (and NP-complete when discretised) for any constant p ≥ 2 or p = 1. Our reduction shows that the geometric 2-connected spanning network problem, i.e., the analogous problem without Steiner points, is also NP-hard for p ≥ 2 or p = 1. [ABSTRACT FROM AUTHOR]
- Subjects :
- *STEINER systems
*COMPUTATIONAL complexity
*NP-hard problems
*BIPARTITE graphs
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 850
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 147341974
- Full Text :
- https://doi.org/10.1016/j.tcs.2020.11.002