Advertisement
Published in:
2012 | OriginalPaper | Chapter
Light Spanners in Bounded Pathwidth Graphs
Authors : Michelangelo Grigni, Hao-Hsiang Hung
Published in: Mathematical Foundations of Computer Science 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given an edge-weighted graph
G
and
ε
> 0, a (1 +
ε
)-spanner is a spanning subgraph
G
′ whose shortest path distances approximate those of
G
within a factor of 1 +
ε
. For
G
from certain graph families (such as bounded genus graphs and apex graphs), we know that
light
spanners exist. That is, we can compute a (1 +
ε
)-spanner
G
′ with total edge weight at most a constant times the weight of a minimum spanning tree. This constant may depend on
ε
and the graph family, but not on the particular graph
G
nor on the edge weighting. The existence of light spanners is essential in the design of approximation schemes for the metric TSP (the traveling salesman problem) and similar graph-metric problems.
In this paper we make some progress towards the conjecture that light spanners exist for every minor-closed graph family: we show that light spanners exist for graphs with bounded pathwidth, and they are computed by a greedy algorithm. We do this via the intermediate construction of light
monotone
spanning trees in such graphs.