...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Kernelization for cycle transversal problems
【24h】

Kernelization for cycle transversal problems

机译：循环横向问题的内核化

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present new kernelization results for two problems, s-cycle transversal and (≤s)-cycle transversal, when s is 4 or 5. We show that 4-cycle transversal and ≤4-cycle transversal admit 6 ~(k2) vertex kernels in general graphs. We then prove NP-completeness of s-cycle transversal and (≤s)-cycle transversal in planar graphs for s>3. We show the following linear vertex kernels in planar graphsa 74k vertex kernel for 4-cycle transversal; a 32k vertex kernel for (≤4)-cycle transversal; a 266k vertex kernel for (≤5)-cycle transversal.
机译：当s为4或5时，我们针对s循环横向和（≤s）循环横向两个问题给出了新的内核化结果。我们显示了4循环横向和≤4循环横向接纳6〜（k2）个顶点内核在一般图中。然后，我们在平面图中针对s> 3证明了s循环横向和（≤s）循环横向的NP完全性。我们在平面graphsa 74k顶点核中显示以下线性顶点核，用于4周期横向;用于（≤4）个循环遍历的32k顶点内核;用于（≤5）周期横向的266k顶点内核。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号