...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International Journal of Foundations of Computer Science >Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree
【24h】

Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

机译：在有界树木和有界度的标记图中提高了最大常见子图问题的硬度

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

摘要

We consider the maximum common connected edge subgraph problem and the maximum common connected induced subgraph problem for simple graphs with labeled vertices (or labeled edges). The former is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs. The latter is to find a common connected induced subgraph with the maximum number of vertices. We prove that both problems are NP-hard for 3-outerplanar labeled graphs even if the maximum vertex degree is bounded by 4. Since the reductions used in the proofs construct graphs with treewidth at most 4, both problems are NP-hard also for such graphs, which significantly improves the previous hardness results for graphs with treewidth 11. We also present improved exponential-time algorithms for both problems on labeled graphs of bounded treewidth and bounded vertex degree.
机译：我们考虑最大的共同连接边缘问题和具有标记顶点（或标记边缘）的简单图形的最大公共连接引起的子图问题。 前者是找到具有最大数量的连接图，该边缘是两个输入图中的每一个的子图的异构。 后者是找到具有最大顶点数量的通用连接的诱导子图。 我们证明，即使最大顶点度为界定的最大顶点度为4，我们也证明这两个问题都是NP-HARD标记图。由于在最多4个用树宽地构造图形中使用的图形来缩短图表，因此也是如此 图表显着改善了具有树木宽度11的图形的先前硬度结果。我们还为有界树木和有界顶点和有界顶点度的标记图的问题提供了改进的指数算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号