Connected Feedback Vertex Set in Planar Graphs
Connected Feedback Vertex Set in Planar Graphs
复制标题
平面图中的连通反馈顶点集
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
René Sitters
中科院分区：
文献类型：
--
作者：
A. Grigoriev;René Sitters
我们研究的问题是找到一个最小的树，跨越给定平面图的各个面。我们证明，如果最小阶数为 3，则无连接版本的近似值为常数因子。此外，我们还提出了一种多项式时间近似方案，适用于有连接和无连接版本。
We study the problem of finding a minimum tree spanning the faces of a given planar graph. We show that a constant factor approximation follows from the unconnected version if the minimum degree is 3. Moreover, we present a polynomial time approximation scheme for both the connected and unconnected version.