Kernelization Using Structural Parameters on Sparse Graph Classes
Kernelization Using Structural Parameters on Sparse Graph Classes
复制标题
在稀疏图类上使用结构参数进行核化
DOI：
10.1007/978-3-642-40450-4_45
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Somnath Sikdar
中科院分区：
文献类型：
--
作者：
Jakub Gajarský;Petr Hlinený;Jan Obdrzálek;Sebastian Ordyniak;Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil;Somnath Sikdar
我们证明了有限整数指数的图问题具有线性核的有界扩展的图时，参数化的调制器的大小恒定树深度图。对于无处稠密的图类，我们的结果产生几乎线性的内核。我们还认为，这样的线性核化结果与较弱的参数将无法包括我们的框架所涵盖的一些问题。我们只要求问题在树深不变的图上有固定的FIS。这允许证明线性核也为问题，如最长路径/循环，精确s，t路径，树宽和路径宽度，这些问题在一般图上没有FIS。
We prove that graph problems with finite integer index have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For nowhere dense graph classes, our result yields almost-linear kernels. We also argue that such a linear kernelization result with a weaker parameter would fail to include some of the problems covered by our framework. We only require the problems to have FII on graphs of constant treedepth. This allows to prove linear kernels also for problems such as Longest-Path/Cycle, Exact-s, t-Path, Treewidth, and Pathwidth, which do not have FII on general graphs.
登录
查看更多内容
影响因子：
1
作者：
COURCELLE, B
通讯作者：
COURCELLE, B
图的路径宽度和树宽度的高效且有建设性的算法
DOI：
10.1006/jagm.1996.0049
发表时间：
1993
期刊：
J. Algorithms
影响因子：
--
作者：
H. Bodlaender;T. Kloks
通讯作者：
T. Kloks
DOI：
--
发表时间：
2011
期刊：
International Symposium on Parameterized and Exact Computation
影响因子：
--
作者：
B. Jansen;Stefan Kratsch
通讯作者：
Stefan Kratsch
Twin-Cover：参数化算法中超越顶点覆盖
DOI：
--
发表时间：
2011
期刊：
International Symposium on Parameterized and Exact Computation
影响因子：
--
作者：
R. Ganian
通讯作者：
R. Ganian
DOI：
--
发表时间：
2012
期刊：
Scandinavian Workshop on Algorithm Theory
影响因子：
--
作者：
H. Bodlaender;B. Jansen;Stefan Kratsch
通讯作者：
Stefan Kratsch