ﻻ يوجد ملخص باللغة العربية
Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a small-complexity graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1. Construction of a light subset spanner. Given a subset of vertices called terminals, and $epsilon$, in polynomial time we construct a subgraph that preserves all pairwise distances between terminals up to a multiplicative $1+epsilon$ factor, of total weight at most $O_{epsilon}(1)$ times the weight of the minimal Steiner tree spanning the terminals. 2. Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion $epsilon D$. Namely, given a minor free graph $G=(V,E,w)$ of diameter $D$, and parameter $epsilon$, we construct a distribution $mathcal{D}$ over dominating metric embeddings into treewidth-$O_{epsilon}(log n)$ graphs such that the additive distortion is at most $epsilon D$. One of our important technical contributions is a novel framework that allows us to reduce emph{both problems} to problems on simpler graphs of bounded diameter. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for vehicle routing with bounded capacity in minor-free metrics; (3) the first efficient approximation scheme for vehicle routing with bounded capacity on bounded genus metrics.
In the Group Steiner Tree problem (GST), we are given a (vertex or edge)-weighted graph $G=(V,E)$ on $n$ vertices, a root vertex $r$ and a collection of groups ${S_i}_{iin[h]}: S_isubseteq V(G)$. The goal is to find a min-cost subgraph $H$ that conne
We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $Gamma$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio bet
In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line
Let $M=(m_{ij})$ be a symmetric matrix of order $n$ whose elements lie in an arbitrary field $mathbb{F}$, and let $G$ be the graph with vertex set ${1,ldots,n}$ such that distinct vertices $i$ and $j$ are adjacent if and only if $m_{ij} eq 0$. We in
A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing t