Before revision: 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.
After revision: 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 . The update time of our algorithm matches the best known static algorithm up to polylogarithmic factors.