Given a weighted undirected graph G=(V,E,w), a hopset H of hopbound \beta and stretch (1+\epsilon) is a set of edges such that for any pair of nodes u, v \in V, there is a path in G \cup H of at most \beta hops, whose length is within a (1+\epsilon) factor from the distance between u and v in G. We provide a decremental algorithm for maintaining hopsets with a polylogarithmic hopbound , with a total update time that matches the best known static algorithm up to polylogarithmic factors.
<clarity> Given a weighted undirected graph G=(V,E,w), a hopset H of hopbound \beta and stretch (1+\epsilon) is a set of edges such that for any pair of nodes u, v \in V, there is a path in G \cup H of at most \beta hops, whose length is within a (1+\epsilon) factor from the distance between u and v in G. We provide a decremental algorithm for maintaining hopsets with a polylogarithmic hopbound , with a total update time that matches the best known static algorithm up to polylogarithmic factors.
Given a weighted undirected graph G=(V,E,w), a hopset H of hopbound \beta and stretch (1+\epsilon) is a set of edges such that for any pair of nodes u, v \in V, there is a path in G \cup H of at most \beta hops, whose length is within a (1+\epsilon) factor from the distance between u and v in G. We show the first efficient decremental algorithm for maintaining hopsets with a polylogarithmic hopbound , with a total update time that matches the best known static algorithm up to polylogarithmic factors.