Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems
Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems
复制标题
将平面图嵌入到低树宽图中，并应用于度量问题的高效近似方案
DOI：
10.1137/1.9781611975482.66
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Eli Fox-Epstein, Eli
Klein
中科院分区：
文献类型：
--
作者：
Eli Fox-Epstein, Eli
Klein
我们证明了，对于任何n> 0，存在直径为D的边加权平面图到有界树宽图的确定性嵌入。利用这个构造得到了加权平面图寻址k-中心（等价d-支配）的第一有效双准则逼近方案，以及独立集的度量推广d-independentSET.近似方案采用度量推广贝克的框架，是基于我们的嵌入结果。
We show that, for any∊> 0, there is a deterministic embedding of edge-weighted planar graphs of diameter D into bounded-treewidth graphs. The embedding has additive error∊D.We use this construction to obtain the firstefficientbicriteria approximation schemes for weighted planar graphs addressingk-Center(equivalentlyd-Domination), and a metric generalization of independent set,d-independentSET. The approximation schemes employ a metric generalization of Baker's framework that is based on our embedding result.