Bundling all shortest paths

Michał Dębski , Konstanty Junosza-Szaniawski , Zbigniew Lonc

Abstract

We study the problem of finding a minimum bundling set in a graph, where a bundling set B is a set 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 set B in a weighted graph G, after some preprocessing using O(|B||V(G)|) memory, it is possible to determine the distance between any two vertices in 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 Gthe 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 Θ(logn/loglogn) trianglefree graphs are needed to cover a complete graph on n vertices, which may be of independent interest.
Author Michał Dębski (FMIS / DAC)
Michał Dębski,,
- Department of Algebra and Combinatorics
, Konstanty Junosza-Szaniawski (FMIS / DAC)
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Zbigniew Lonc (FMIS / DAC)
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X, e-ISSN 1872-6771
Issue year2020
Vol277
Pages82-91
Publication size in sheets0.5
Keywords in Polishnajktótsza ścieżka, pokrycie ścieżek, algorytm ATL
Keywords in EnglishShortest path, Path covering, ALT algorithm
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
Abstract in PolishArtykuł dotyczy problemu minimalnego zbioru wiążącego w grafie. Zbiór wierzchołków B w grafie jest zbiorem wiążącym jeśli, każda najkrótsza ścieżka może być przedłużona do najkrótszej ścieżki o przynajmniej jednym końcu w zbiorze B. Przez b(G) oznaczamy liczność najmniejszego zbioru wiążącego w grafie ważonym G. Zbiór wiążący może być wykorzystany w algorytmie ALT do znajdowania najkrótszych ścieżek w grafie. Dla ustalonego zbioru wiążącego B w grafie ważonym G po pewnych obliczeniach wstępnych, z wykorzystaniem O(|B||V(G)|) pamięci, można wyznaczyć odległość dwóch wierzchołków w czasie O(|B|). Dlatego też istotne jest aby znaleźć zbiór wiążący jak najmniejszej liczności. Dowodzimy, że wyznaczenie b(G) jest zagadnieniem NP-trudnym przedstawiamy 2-approksymacyjny algorytm. Ponadto przedstawiamy charakterystykę grafy o jednoelementowym zbiorze wiążącym oraz podgrafy gridu o 2-elementowym zbiorze wiążącym. Ponadto przedstawiamy parametr b∗(G) równy minimum z b(H) po wszystkich izometrycznych nadgrafach H grafu G. Parametr b∗(G) może być istotnie mniejszy od b(G) co dodatkowo może przyspieszyć algorytm ATL. W dowodzie jednego z twierdzeń, otrzymujemy, że Θ(logn/loglogn) grafów bez trójkątów jest potrzebnych do pokrycia krawędzi grafu pełnego, co może interesującym wynikiem niezależnie od algorytmu ATL.
DOIDOI:10.1016/j.dam.2019.08.027
URL https://www.sciencedirect.com/science/article/abs/pii/S0166218X19304007
Languageen angielski
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 23-09-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.263; WoS Impact Factor: 2018 = 0.983 (2) - 2018=1.029 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?