Bundling all shortest paths

Investor logo

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

DĘBSKI Michał Karol JUNOSZA-SZANIAWSKI Konstanty LONC Zbigniew

Year of publication 2020
Type Article in Periodical
Magazine / Source Discrete Applied Mathematics
MU Faculty or unit

Faculty of Informatics

Citation
web https://doi.org/10.1016/j.dam.2019.08.027
Doi http://dx.doi.org/10.1016/j.dam.2019.08.027
Keywords shortest paths; ALT algorithm
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info