| Texto completo | |
| Autor(es): |
Gomez, Renzo
;
Miyazawa, Flavio Keidi
;
Wakabayashi, Yoshiko
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | THEORETICAL COMPUTER SCIENCE; v. 947, p. 13-pg., 2023-01-19. |
| Resumo | |
For a constant t > 1, a t-spanner of a connected graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times its distance in G. This concept, introduced by Peleg and Ullman in 1989, was used in the construction of an optimal synchronizer for the hypercube. We address the problem of finding a t-spanner with minimum number of edges. This problem is called the minimum t-spanner problem (MINSt), and is known to be NP-hard for every t > 2 even on bounded-degree graphs. Our main contribution is to improve the previous results, by showing that MINSt is NP-hard even on planar graphs with maximum degree at most 4 (resp. 5) when t > 4 (resp. t = 3). We also show that with a slight modification of a result presented by Kobayashi (2018), MINS2 remains NP-hard on planar graphs with maximum degree 7.(c) 2023 Elsevier B.V. All rights reserved. (AU) | |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 19/14471-1 - Problemas sobre spanners em grafos |
| Beneficiário: | Renzo Gonzalo Gómez Diaz |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Processo FAPESP: | 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos |
| Beneficiário: | Reinaldo Morabito Neto |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |