Computer Science – Data Structures and Algorithms
Scientific paper
2011-04-25
Computer Science
Data Structures and Algorithms
10 pages, 3 figures
Scientific paper
Given an edge-weighted graph $G$ and $\epsilon>0$, a $(1+\epsilon)$-spanner is a spanning subgraph $G'$ whose shortest path distances approximate those of $G$ within a $(1+\epsilon)$ factor. If $G$ is from certain minor-closed graph families (at least bounded genus graphs and apex graphs), then we know that light spanners exist. That is, we can compute a $(1+\epsilon)$-spanner $G'$ with total edge weight at most a constant times the weight of a minimum spanning tree. This constant may depend on $\epsilon$ and the graph family, but not on the particular graph $G$ nor on its edge weighting. For weighted graphs from several minor-closed graph families, the existence of light spanners has been essential in the design of approximation schemes for the metric TSP (the traveling salesman problem) and some similar problems. In this paper we make some progress towards the conjecture that light spanners exist for every minor-closed graph family. In particular, we show that they exist for graphs with bounded pathwidth. We do this via the construction of light enough monotone spanning trees in such graphs.
Grigni Michelangelo
Hung Hao-Hsiang
No associations
LandOfFree
Finding Light Spanners in Bounded Pathwidth Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finding Light Spanners in Bounded Pathwidth Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Light Spanners in Bounded Pathwidth Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-544471