Heuristic-based computation of tailored spanning trees to speed up compact planar graphs

Simple item page
UDC.coleccionInvestigación
UDC.departamentoCiencias da Computación e Tecnoloxías da Información
UDC.endPage1484
UDC.grupoInvLaboratorio de Bases de Datos (LBD)
UDC.institutoCentroCITIC - Centro de Investigación de Tecnoloxías da Información e da Comunicación
UDC.issue10
UDC.journalTitleThe Computer Journal
UDC.startPage1476
UDC.volume68
dc.contributor.authorIrribarra-Cortés, Ayleen
dc.contributor.authorAsín-Achá, Roberto
dc.contributor.authorFuentes Sepúlveda, José
dc.contributor.authorSeco, Diego
dc.date.accessioned2025-11-12T09:13:46Z
dc.date.available2025-11-12T09:13:46Z
dc.date.issued2025-05-14
dc.descriptionThis is a pre-copyedited, author-produced version of an article accepted for publication in The Computer Journal following peer review. The version of record Ayleen Irribarra-Cortés, Roberto Asín-Achá, José Fuentes-Sepúlveda, Diego Seco, Heuristic-based computation of tailored spanning trees to speed up compact planar graphs, The Computer Journal, Volume 68, Issue 10, October 2025, Pages 1476–1484, is available online at: https://doi.org/10.1093/comjnl/bxaf051 The data and code of this article are available on public repositories. The implementation is available at the GitHub repository mentioned in Section 4.1. The datasets are available in the repository mentioned on Section 4.2.
dc.description.abstract[Abstract]: In this work we address the problem of speeding up navigational queries over compact planar graphs. In particular, we work over one of the most practical representations for compact planar graphs, which is based on the decomposition of the graph into one arbitrary spanning tree and a second one induced by the former. We propose a new optimization model that captures the desired topological properties of the first spanning tree. For this model, we propose several heuristics, which we experimentally compare on our application domain. The experimental results support that the model indeed captures the main properties that allow us speeding up the main navigational queries over several benchmarks.
dc.description.sponsorshipThis work was funded by ANID – Millennium Science Initiative Program – Code ICN17 002, Chile (1st and 3rd authors), PAI grant 77190038 (3rd author), FONDECYT grant 11220545 (3rd author), PFCHA / Doctorado Nacional / 2021-21211768 (1st author), TED2021-129245B-C21 (PLAGEMIS) and PID2020-114635RB-I00 (EXTRACompact): partially funded by MCIN/AEI/10.13039/501100011033 and “NextGenerationEU”/PRTR, GRC: ED431C 2021/53, partially funded by GAIN/Xunta de Galicia [4th author]. CITIC is funded by the Xunta de Galicia through the collaboration agreement between the Department of Culture, Education, Vocational Training and Universities and the Galician universities for the reinforcement of the research centers of the Galician University System (CIGUS).
dc.description.sponsorshipChile. Agencia National de Investigación y Desarrollo; ICN17_002
dc.description.sponsorshipChile. Agencia National de Investigación y Desarrollo; 77190038
dc.description.sponsorshipChile. Fondo Nacional de Desarrollo Científico y Tecnológico; 11220545
dc.description.sponsorshipXunta de Galicia; ED431C 2021/53
dc.identifier.citationAyleen Irribarra-Cortés, Roberto Asín-Achá, José Fuentes-Sepúlveda, Diego Seco, Heuristic-based computation of tailored spanning trees to speed up compact planar graphs, The Computer Journal, Volume 68, Issue 10, October 2025, Pages 1476–1484, https://doi.org/10.1093/comjnl/bxaf051
dc.identifier.doi10.1093/comjnl/bxaf051
dc.identifier.issn1460-2067
dc.identifier.urihttps://hdl.handle.net/2183/46415
dc.language.isoeng
dc.publisherOxford
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/TED2021-129245B-C21/ES/PLATAFORMA PARA LA GENERACIÓN AUTOMÁTICA DE SISTEMAS DE INFORMACIÓN DE LA MOVILIDAD ENERGÉTICAMENTE EFICIENTES, BASADOS EN ESTRUCTURAS DE DATOS COMPACTAS Y GIS (PLAGEMIS)
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-114635RB-I00/ES/EXPLOTACION ENRIQUECIDA DE TRAYECTORIAS CON ESTRUCTURAS DE DATOS COMPACTAS Y GIS/
dc.relation.urihttps://doi.org/10.1093/comjnl/bxaf051
dc.rights© The British Computer Society 2025
dc.rights.accessRightsopen access
dc.subjectCompact data structure
dc.subjectPlanar graph
dc.subjectCombinatorial optimization
dc.subjectHeuristics
dc.titleHeuristic-based computation of tailored spanning trees to speed up compact planar graphs
dc.typejournal article
dc.type.hasVersionAM
dspace.entity.typePublication
relation.isAuthorOfPublication205d0115-1d0f-46c4-8581-ea7a69642870
relation.isAuthorOfPublication.latestForDiscovery205d0115-1d0f-46c4-8581-ea7a69642870

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Seco_Diego_2025_Heuristic_based_computation_of_tailored_spanning_trees.pdf
Size:
798.26 KB
Format:
Adobe Portable Document Format
Download

Collections

Investigación (FIC)