Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
复制标题
短僻 sâtâpath 问题的参数化算法和数据缩减
DOI：
10.1002/net.21904
复制
发表时间：
2020
期刊：
影响因子：
2.1
通讯作者：
O. Y. Tsidulko
中科院分区：
文献类型：
--
作者：
R. van Bevern;T. Fluschnik;O. Y. Tsidulko
给定一个图G=1(V，E)，两个顶点t∈V和两个整数ℓ，最短隐蔽路径问题是找到一条有最多顶点和ℓ邻居的简单t路。我们研究了该问题关于四个结构图参数的参数化复杂性：顶点覆盖数、树宽、反馈顶点数和反馈边数。特别地，我们完全解决了在这些参数中存在尺寸多项式的问题核及其与ℓ的组合问题。我们还得到了树宽tw的n-顶点图的一个2O(Tw)· ℓ2·n次算法，它给出了几类图的次指数时间算法。
Given a graphG= (V,E), two verticess,t∈V, and two integersk,ℓ, theShort Secluded Pathproblem is to find a simples‐t‐path with at mostkvertices andℓneighbors. We study the parameterized complexity of the problem with respect to four structural graph parameters: the vertex cover number, treewidth, feedback vertex number, and feedback edge number. In particular, we completely settle the question of the existence of problem kernels with size polynomial in these parameters and their combinations withkandℓ. We also obtain a 2O(tw)· ℓ2·n‐time algorithm forn‐vertex graphs of treewidth tw, which yields subexponential‐time algorithms in several graph classes.
登录
查看更多内容
混合多风电容弧路由问题的参数化近似算法：理论与实验
影响因子：
2.1
作者：
R. van Bevern;C. Komusiewicz;und M. Sorge
通讯作者：
und M. Sorge
用于安全车队路线的参数化算法和数据缩减
DOI：
--
发表时间：
2018
期刊：
Algorithmic Approaches for Transportation Modeling, Optimization, and Systems
影响因子：
--
作者：
René van Bevern;T. Fluschnik;O. Tsidulko
通讯作者：
O. Tsidulko
影响因子：
0.5
作者：
F. Fomin;P. Golovach;Nikolai Karpov;A. Kulikov
通讯作者：
A. Kulikov
影响因子：
1.6
作者：
Bodlaender, Hans L.;Drange, Pal Gronas;Pilipczuk, Micha L.
通讯作者：
Pilipczuk, Micha L.
通过在稀疏图中找到更多交叉来改进交叉引理
影响因子：
0.8
作者：
J. Pach;R. Radoicic;G. Tardos;G. Tóth
通讯作者：
G. Tóth