%AAhmed, R.%AHamm, K.%AJebelli, M.%AKobourov, S.%ASahneh, F.%ASpence, R.%BJournal Name: Symposium on Experimental Algorithms
%D2019%I
%JJournal Name: Symposium on Experimental Algorithms
%K
%MOSTI ID: 10109412
%PMedium: X
%TApproximation algorithms and an integer program for multi-level graph spanners
%XGiven a weighted graph G(V, E) and t ≥ 1, a subgraph H is a t–spanner of G if the lengths of shortest paths in G are preserved in H up to a multiplicative factor of t. The subsetwise spanner problem aims to preserve distances in G for only a subset of the vertices. We generalize the minimum-cost subsetwise spanner problem to one where vertices appear on multiple levels, which we call the multi-level graph spanner (MLGS) problem, and describe two simple heuristics. Applications of this problem include road/network building and multi-level graph visualization, especially where vertices may require different grades of service.
We formulate a 0–1 integer linear program (ILP) of size O(|E||V |2) for the more general minimum pairwise spanner problem, which resolves an open question by Sigurd and Zachariasen on whether this problem admits a useful polynomial-size ILP. We extend this ILP formulation to the MLGS problem, and evaluate the heuristic and ILP performance on random graphs of up to 100 vertices and 500 edges.
%0Journal Article
Country unknown/Code not availableOSTI-MSA