Další formáty:
BibTeX
LaTeX
RIS
@article{1645756,
author = {Dębski, Michał Karol and JunoszaandSzaniawski, Konstanty and Lonc, Zbigniew},
article_number = {1},
doi = {http://dx.doi.org/10.1016/j.dam.2019.08.027},
keywords = {shortest paths; ALT algorithm},
language = {eng},
issn = {0166-218X},
journal = {Discrete Applied Mathematics},
title = {Bundling all shortest paths},
url = {https://doi.org/10.1016/j.dam.2019.08.027},
volume = {277},
year = {2020}
}
TY - JOUR
ID - 1645756
AU - Dębski, Michał Karol - Junosza-Szaniawski, Konstanty - Lonc, Zbigniew
PY - 2020
TI - Bundling all shortest paths
JF - Discrete Applied Mathematics
VL - 277
IS - 1
SP - 82-91
EP - 82-91
PB - Elsevier Science
SN - 0166218X
KW - shortest paths
KW - ALT algorithm
UR - https://doi.org/10.1016/j.dam.2019.08.027
L2 - https://doi.org/10.1016/j.dam.2019.08.027
N2 - We study the problem of finding a minimum bundling set in a graph, where a bundling set is a set B of vertices such that every shortest path can be extended to a shortest path from a vertex in B to some other vertex. If G is a weighted graph, we denote the size of a minimum bundling set in G by b(G). Bundling sets can be used by the ALT algorithm that finds shortest paths in weighted graphs. For a fixed bundling setBin a weighted graph G, after some preprocessing using O(|B||V(G)|) memory, it is possible to determine the distance between any two verticesin time O(|B|). Therefore, it is desirable to find small bundling sets. We show that determining b(G) is NP-hard and give a 2-approximation algorithm. Moreover we characterize simple graphs with b=1 and subgraphs of grids with b=2. We also introduce the parameter b*(G) equal to the minimum of b(H) over all weighted graphs H such that G is an isometric subgraph of H, i.e. for every two vertices u, v of G the distances from u to v in G and in H are the same. Sometimes b*(G) is much smaller than b(G) and a further improvement of performance of route planning can be obtained. As a part of a proof, we show that at least Theta(logn/loglogn) triangle-free graphs are needed to cover a complete graph on n vertices, which may be of independent interest.
ER -
DĘBSKI, Michał Karol, Konstanty JUNOSZA-SZANIAWSKI a Zbigniew LONC. Bundling all shortest paths. \textit{Discrete Applied Mathematics}. Elsevier Science, 2020, roč.~277, č.~1, s.~82-91. ISSN~0166-218X. Dostupné z: https://dx.doi.org/10.1016/j.dam.2019.08.027.
|
