English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Understanding the structure of minor-free metrics, namely shortest pathmetrics obtained over a weighted graph excluding a fixed minor, has been animportant research direction since the fundamental work of Robertson andSeymour. A fundamental idea that helps both to understand the structuralproperties of these metrics and lead to strong algorithmic results is toconstruct a "small-complexity" graph that approximately preserves distancesbetween pairs of points of the metric. We show the two following structuralresults for minor-free metrics:  1. Construction of a light subset spanner. Given a subset of vertices calledterminals, and $\epsilon$, in polynomial time we construct a subgraph thatpreserves all pairwise distances between terminals up to a multiplicative$1+\epsilon$ factor, of total weight at most $O_{\epsilon}(1)$ times the weightof the minimal Steiner tree spanning the terminals.  2. Construction of a stochastic metric embedding into low treewidth graphswith expected additive distortion $\epsilon D$. Namely, given a minor freegraph $G=(V,E,w)$ of diameter $D$, and parameter $\epsilon$, we construct adistribution $\mathcal{D}$ over dominating metric embeddings intotreewidth-$O_{\epsilon}(\log n)$ graphs such that the additive distortion is atmost $\epsilon D$.  One of our important technical contributions is a novel framework that allowsus to reduce \emph{both problems} to problems on simpler graphs of boundeddiameter. Our results have the following algorithmic consequences: (1) thefirst efficient approximation scheme for subset TSP in minor-free metrics; (2)the first approximation scheme for vehicle routing with bounded capacity inminor-free metrics; (3) the first efficient approximation scheme for vehiclerouting with bounded capacity on bounded genus metrics.

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs