...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On the complexity of the approximation of nonplanarity parameters for cubic graphs
【24h】

On the complexity of the approximation of nonplanarity parameters for cubic graphs

机译：关于三次图非平面参数逼近的复杂性

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

摘要

Let G=(V,E) be a simple graph. The NON-PLANAR DELETION problem consists in finding a smallest subset E' is contained in E such that H = (V,EE') is a planar graph. The SPLITTING NUMBER problem consists in finding the smallest integer k ≥ 0, such that a planar graph H can be defined from G by k vertex splitting operations. We establish the Max SNP-hardness of SPLITTING NUMBER and NON-PLANAR DELETION problems for cubic graphs.
机译：令G =（V，E）为简单图。非平面删除问题在于找到E中包含的最小子集E'，使得H =（V，E E'）是平面图。分裂数问题在于找到最小的整数k≥0，以便可以通过k个顶点分裂操作从G定义平面图H。我们建立了分裂图的最大SNP硬度和三次图的非平面删除问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号