Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
复制标题
排除单交叉图作为次要图类的近似算法
DOI：
10.1016/j.jcss.2003.12.001
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
D. Thilikos
中科院分区：
文献类型：
--
作者：
E. Demaine;M. Hajiaghayi;N. Nishimura;P. Ragde;D. Thilikos
许多问题是棘手的一般图允许多项式时间解决方案的结构类的图，如平面图和图的有界树宽。在本文中，我们证明了结构性质的较大类的图，并展示了如何利用的性质，以获得算法。类被认为是那些形成的排除作为一个未成年人的图，可以嵌入在平面上，最多一个交叉。我们表明，在这些类中的图可以分解成平面图和图的小树宽，我们使用的分解，以显示所有这样的图有局部有界树宽（一定形式的所有子图是图的有界树宽）。最后，我们利用的结构特性，推导出多项式时间算法近似树宽在一个因素为1.5和分支宽度在一个因素为2.25，以及多项式时间的近似计划的最小化和最大化的问题和固定参数的算法，如顶点覆盖，边支配集，反馈顶点集等问题。
Many problems that are intractable for general graphs allow polynomial-time solutions for structured classes of graphs, such as planar graphs and graphs of bounded treewidth. In this paper, we demonstrate structural properties of larger classes of graphs and show how to exploit the properties to obtain algorithms. The classes considered are those formed by excluding as a minor a graph that can be embedded in the plane with at most one crossing. We show that graphs in these classes can be decomposed into planar graphs and graphs of small treewidth; we use the decomposition to show that all such graphs have locally bounded treewidth (all subgraphs of a certain form are graphs of bounded treewidth). Finally, we make use of the structural properties to derive polynomial-time algorithms for approximating treewidth within a factor of 1.5 and branchwidth within a factor of 2.25 as well as polynomial-time approximation schemes for both minimization and maximization problems and fixed-parameter algorithms for problems such as vertex cover, edge-dominating set, feedback vertex set, and others.