skip to main content

Search for: All records

Creators/Authors contains: "Jebelli, M."

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Given 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.