2026-07-22T06:32:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7503 2024-03-06T10:40:18Z ddc:004 open_access

Efficient Construction of Probabilistic Tree Embeddings Blelloch, Guy E. Gu, Yan Sun, Yihan Graph Algorithm Metric Embeddings Probabilistic Tree Embeddings Single-source Shortest-paths In this paper we describe an algorithm that embeds a graph metric (V,d_G) on an undirected weighted graph G=(V,E) into a distribution of tree metrics (T,D_T) such that for every pair u,v in V, d_G(u,v)<=d_T(u,v) and E_T[d_T(u,v)]<=O(log n)d_G(u,v). Such embeddings have proved highly useful in designing fast approximation algorithms, as many hard problems on graphs are easy to solve on tree instances. For a graph with n vertices and m edges, our algorithm runs in O(m log n) time with high probability, which improves the previous upper bound of O(m log^3 n) shown by Mendel et al. in 2009. The key component of our algorithm is a new approximate single-source shortest-path algorithm, which implements the priority queue with a new data structure, the bucket-tree structure. The algorithm has three properties: it only requires linear time in terms of the number of edges in the input graph; the computed distances have the distance preserving property; and when computing the shortest-paths to the k-nearest vertices from the source, it only requires to visit these vertices and their edge lists. These properties are essential to guarantee the correctness and the stated work bound. Using this shortest-path algorithm, we show how to generate an intermediate structure, the approximate dominance sequences of the input graph, in O(m log n) time, and further propose a simple yet efficient algorithm to converted this sequence to a tree embedding in O(n log n) time, both with high probability. Combining the three subroutines gives the stated work bound of the algorithm. We also show a new application of probabilistic tree embeddings: they can be used to accelerate the construction of a series of approximate distance oracles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guy E. Blelloch and Yan Gu and Yihan Sun 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.26 urn:nbn:de:0030-drops-75034 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.26 eng https://creativecommons.org/licenses/by/3.0/legalcode