• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-theoretic concepts in computer science >Finding Induced Paths of Given Parity in Claw-Free Graphs
【24h】

Finding Induced Paths of Given Parity in Claw-Free Graphs

机译：在无爪图中寻找给定奇偶校验的诱导路径

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

摘要

The Parity Path problem is to decide if a given graph G contains both an odd length and an even length induced path between two specified vertices s and t. In the related problems Odd Induced Path and Even Induced Path,the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in (O)(n5) time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in (O)(n5) time and (O)(n7) time, respectively. We also show that we can decide in (O)(n7) time whether a claw-free graph has an induced cycle of given parity through a specified vertex.
机译：奇偶校验路径问题是确定给定图G是否同时包含两个指定顶点s和t之间的奇数长度和偶数长度引起的路径。在相关的奇数诱导路径和偶数诱导路径问题中，目标是确定两个指定顶点之间是否存在奇数或偶数长度的诱导路径。尽管所有这三个问题通常都是NP完全的，但我们证明对于无爪图类，它们可以在（O）（n5）时间内解决。如果从G中的s到t的每个诱导路径都具有偶数长度，则两个顶点s和t在G中形成偶数对。我们的结果表明，可以在（O）（）中解决确定无爪图的两个指定顶点是否形成偶数对的问题以及确定给定无爪图是否具有偶数对的问题。 n5）时间和（O）（n7）时间。我们还表明，我们可以在（O）（n7）时间内确定无爪图是否具有通过指定顶点的给定奇偶校验的诱导周期。

著录项

  • 来源
  • 会议地点 Montpellier(FR);Montpellier(FR)
  • 作者

    Pim van t Hof; Marcin Kaminski; Daniel Paulusma;

  • 作者单位

    Department of Computer Science, University of Durham,Science Laboratories, South Road, Durham DH1 3LE, England;

    Computer Science Department, Universite Libre de Bruxelles,Boulevard du Triomphe CP212, B-1050 Brussels, Belgium;

    Department of Computer Science, University of Durham,Science Laboratories, South Road, Durham DH1 3LE, England;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算机网络;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号