Mostrar o rexistro simple do ítem
Resolving Sets Tolerant to Failures in Three-Dimensional Grids
dc.contributor.author | Mora, Mercè | |
dc.contributor.author | Souto Salorio, María José | |
dc.contributor.author | Tarrío-Tobar, Ana D. | |
dc.date.accessioned | 2022-09-06T11:32:55Z | |
dc.date.available | 2022-09-06T11:32:55Z | |
dc.date.issued | 2022 | |
dc.identifier.citation | Mora, M., Souto-Salorio, M.J. & Tarrío-Tobar, A.D. Resolving sets tolerant to failures in three-dimensional grids. Mediterr. J. Math. 19, 188 (2022). https://doi.org/10.1007/s00009-022-02096-1 | es_ES |
dc.identifier.issn | 1660-5454 | |
dc.identifier.uri | http://hdl.handle.net/2183/31517 | |
dc.description.abstract | [Abstract] An ordered set S of vertices of a graph G is a resolving set for G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set. In this paper we study resolving sets tolerant to several failures in three-dimensional grids. Concretely, we seek for minimum cardinality sets that are resolving after removing any k vertices from the set. This is equivalent to finding (k+1)-resolving sets, a generalization of resolving sets, where, for every pair of vertices, the vector of distances to the vertices of the set differs in at least k+1 coordinates. This problem is also related with the study of the (k+1)-metric dimension of a graph, defined as the minimum cardinality of a (k+1)-resolving set. In this work, we first prove that the metric dimension of a three-dimensional grid is 3 and establish some properties involving resolving sets in these graphs. Secondly, we determine the values of k≥1 for which there exists a (k+1)-resolving set and construct such a resolving set of minimum cardinality in almost all cases. | es_ES |
dc.description.sponsorship | This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. M. Mora is supported by projects H2020-MSCA-RISE-2016-734922 CONNECT, PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation and Gen.Cat. DGR2017SGR1336; M. J. Souto-Salorio is supported by project PID2020-113230RB-C21 of the Spanish Ministry of Science and Innovation. Open Access funding provided thanks to the CRUECSIC agreement with Springer Nature | es_ES |
dc.description.sponsorship | Generalitat de Catalunya; DGR2017SGR1336 | |
dc.language.iso | eng | es_ES |
dc.publisher | Springer Nature | es_ES |
dc.relation | info:eu-repo/grantAgreement/EC/H2020/12345/734922 | es_ES |
dc.relation | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-104129GB-I00/ES/TEORIA Y APLICACIONES DE CONFIGURACIONES DE PUNTOS Y REDES/ | |
dc.relation | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-113230RB-C21/ES/MODELOS MULTITAREA DE ETIQUETADO SECUENCIAL PARA EL RECONOCIMIENTO DE ENTIDADES ENRIQUECIDO CON INFORMACION LINGUISTICA: SINTAXIS E INTEGRACION MULTITAREA (SCANNER-UDC)/ | |
dc.relation.uri | https://doi.org/10.1007/s00009-022-02096-1 | es_ES |
dc.rights | Attribution 4.0 International (CC BY 4.0) | es_ES |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | * |
dc.subject | Resolving set | es_ES |
dc.subject | Metric dimension | es_ES |
dc.subject | k-resolving set | es_ES |
dc.subject | k-metric dimension | es_ES |
dc.subject | Fault-tolerant | es_ES |
dc.subject | Three-dimensional grid | es_ES |
dc.title | Resolving Sets Tolerant to Failures in Three-Dimensional Grids | es_ES |
dc.type | info:eu-repo/semantics/article | es_ES |
dc.rights.access | info:eu-repo/semantics/openAccess | es_ES |
UDC.journalTitle | Mediterranean Journal of Mathematics | es_ES |
UDC.volume | 19 | es_ES |
UDC.issue | 188 | es_ES |
UDC.startPage | 1 | es_ES |
UDC.endPage | 19 | es_ES |
dc.identifier.doi | 10.1007/s00009-022-02096-1 |
Ficheiros no ítem
Este ítem aparece na(s) seguinte(s) colección(s)
-
GI-XDA - Artigos [13]
-
OpenAIRE [342]