Two-Layer Planarization parameterized by feedback edge set
Two-Layer Planarization parameterized by feedback edge set
复制标题
由反馈边缘集参数化的两层平面化
DOI：
10.1016/j.tcs.2013.01.029
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
M. Weller
中科院分区：
文献类型：
--
作者：
J. Uhlmann;M. Weller
给定一个无向图G和一个整数k≥0，NP-hard 2-Layer Planarization问题问的是通过去除最多k条边是否可以将G转化为毛虫树的森林。已知2层平面化相对于参数k是固定参数可处理的。目前的状态是O（3.562k⋅k+|G|）时间搜索树算法和O(k)大小的问题核。由于将G转化为毛虫树的森林需要打破每个循环，因此最小反馈边集的大小f是一个f≤k的自然参数。通过提出新的多项式时间数据约简规则，我们改进了先前关于k的固定参数可追溯性结果，该规则导致了一个具有O(f)个顶点和边的问题核和一个新的基于搜索树的算法。对于大范围的输入实例，我们期望f明显小于k。
Given an undirected graph G and an integer k≥0, the NP-hard 2-Layer Planarization problem asks whether G can be transformed into a forest of caterpillar trees by removing at most k edges. 2-Layer Planarization was known to be fixed-parameter tractable with respect to the parameter k. The state of the art is an O(3.562k⋅k+|G|)-time search tree algorithm and an O(k)-size problem kernel. Since transforming G into a forest of caterpillar trees requires breaking every cycle, the size f of a minimum feedback edge set is a natural parameter with f≤k. We improve on previous fixed-parameter tractability results with respect to k by presenting new polynomial-time data reduction rules leading to a problem kernel with O(f) vertices and edges and a new search-tree based algorithm. We expect f to be significantly smaller than k for a wide range of input instances.
登录
查看更多内容
走向完全多元算法：参数生态学的一些新结果和方向
DOI：
--
发表时间：
2009
期刊：
International Workshop on Combinatorial Algorithms
影响因子：
--
作者：
M. Fellows
通讯作者：
M. Fellows
DOI：
--
发表时间：
2005
期刊：
J. Graph Algorithms Appl.
影响因子：
--
作者：
H. Fernau
通讯作者：
H. Fernau
图算法与应用杂志 Dagmaps：有向无环图的空间填充可视化
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
Vassilis Tsiaras;Sofia Triantafilou;I. Tollis;S.;T. Nishizeki
通讯作者：
T. Nishizeki
DOI：
--
发表时间：
2001
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
F. Shahrokhi;O. Sýkora;L. Székely;I. Vrto
通讯作者：
I. Vrto
分层图形绘制
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
M. Suderman
通讯作者：
M. Suderman