| Full text | |
| Author(s): |
Benedito, Marcelo P. L.
;
Pedrosa, Lehilton L. C.
;
Ferreira, CE
;
Lee, O
;
Miyazawa, FK
Total Authors: 5
|
| Document type: | Journal article |
| Source: | PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 10-pg., 2021-01-01. |
| Abstract | |
In the STAR k-HUB CENTER (SkHC), given a connected edge-weighted graph G, a center c is an element of V(G) and integers k, r >= 0, one wants to select a set of hubs H subset of V(G)\{c} of size k and an assignment from vertices to hubs. The goal is to find a solution in which the length of the longest path connecting each pair of vertices through the assigned hubs and the center is at most r. This problem appears in many areas, such as telecommunication, aviation and logistics, where hubs represent cross-docking centers that consolidate demand between pairs of clients, and the network has a centralized design. This paper investigates the parameterized complexity of the underlying graph connectivity problem. First, we note that finding a (1.25 c)-approximation is W[2]-hard, for E > 0, when the parameter is the number of hubs k. Moreover, we show that the problem is W[1]-hard even when parameterized by k plus the vertex cover number of the graph. While this rules out an algorithm parameterized by the treewidth tw of the graph, as a positive result, we present an efficient parameterized approximation scheme. Namely, for every epsilon > 0, we have a (1 + epsilon)-approximation that runs in time O*((tw/epsilon)(O(tw))). (C) 2021 The Authors. Published by Elsevier B.V. (AU) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 19/10400-2 - Approximation and parameterized algorithms for pair connectivity problems |
| Grantee: | Marcelo Pinheiro Leite Benedito |
| Support Opportunities: | Scholarships in Brazil - Doctorate |