Fixed parameter tractability of a biconnected bottleneck Steiner network problem
| Autor: | Charl J. Ras |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
050210 logistics & transportation 021103 operations research Degree (graph theory) Computer Networks and Communications Plane (geometry) 05 social sciences 0211 other engineering and technologies 02 engineering and technology Bottleneck Constraint (information theory) Set (abstract data type) Hardware and Architecture Simple (abstract algebra) Bounded function 0502 economics and business Enhanced Data Rates for GSM Evolution Software Information Systems Mathematics |
| Zdroj: | Networks. 75:310-320 |
| ISSN: | 1097-0037 0028-3045 |
| DOI: | 10.1002/net.21926 |
| Popis: | For a given set X of points in the plane, we consider the problem of constructing a 2-vertex-connected network spanning X and at most k additional Steiner points such that the length of the longest edge (the so-called bottleneck) of the network is minimized. When one introduces a constraint on the network specifying that all Steiner points must be of degree 2 the problem remains NP-complete but becomes fixed parameter tractable with respect to k. We prove this by presenting an algorithm which solves the degree-2 bounded problem optimally in a time of O(n4k62k), where n = |X|. We also present a simple 3-approximation algorithm for the degree-2 bounded problem and show that the bottleneck length of an optimal solution to the degree-2 bounded problem is at most twice the bottleneck length when degree is not bounded. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text