Bundling all shortest paths

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00115529" target="_blank" >RIV/00216224:14330/20:00115529 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.dam.2019.08.027" target="_blank" >https://doi.org/10.1016/j.dam.2019.08.027</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2019.08.027" target="_blank" >10.1016/j.dam.2019.08.027</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bundling all shortest paths

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Bundling all shortest paths

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_027%2F0008360" target="_blank" >EF16_027/0008360: Postdoc@MUNI</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

277

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

10

Strana od-do

82-91

Kód UT WoS článku

000528193900007

EID výsledku v databázi Scopus

2-s2.0-85072709899