Given a weighted graph @math and @math , a subgraph @math is a of @math if the lengths of shortest paths in @math are preserved in @math up to a multiplicative factor of @math . The problem aims to preserve distances in @math 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 (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 @math for the more general minimum , 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.
Sigurd and Zachariasen @cite_17 present an ILP formulation for the minimum-weight pairwise spanner problem (see ), and show that the greedy algorithm @cite_22 performs well on sparse graphs of up to 64 vertices. ' A lvarez-Miranda and Sinnl @cite_1 present a mixed ILP formulation for the tree @math --spanner problem, which asks for a spanning tree of a graph @math with the smallest stretch factor @math .
@cite_1 @cite_22 @cite_17
2897842022 1489900072 1525064252
The tree (t^* )-spanner problem is an NP-hard problem, which is concerned with finding a spanning tree in a given undirected weighted graph, such that for each pair of nodes the ratio of the shortest distance in the spanning tree and the shortest distance in the given graph is bounded by t. The goal is to find a spanning tree, which gives the minimal t. This problem is associated with many network design applications, but in particular, in the context of architecture of distributed systems. We introduce mixed-integer programming formulations for the tree (t^* )-spanner problem, and present a branch-and-cut solution approach based on these formulations. The branch-and-cut is enhanced with an initialization procedure and a primal heuristic. A computational study is done to assess the effectiveness of our proposed algorithmic strategies. To the best of our knowledge, this is the first time that an exact approach is proposed for this problem. Given a graph G, a subgraph G′ is a t-spanner of G, if for every u, v ∈ V, the distance from u to v in G′ is at most t times longer than the distance in G. In this paper we give a very simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds. Spanners are sparse subgraphs that preserve distances up to a given factor in the underlying graph. Recently spanners have found important practical applications in metric space searching and message distribution in networks. These applications use some variant of the so-called greedy algorithm for constructing the spanner — an algorithm that mimics Kruskal’s minimum spanning tree algorithm. Greedy spanners have nice theoretical properties, but their practical performance with respect to total weight is unknown. In this paper we give an exact algorithm for constructing minimum-weight spanners in arbitrary graphs. By using the solutions (and lower bounds) from this algorithm, we experimentally evaluate the performance of the greedy algorithm for a set of realistic problem instances.