• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On the complexity of recognizing directed path families
【24h】

On the complexity of recognizing directed path families

机译：关于识别定向路径族的复杂性

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

摘要

A Directed Path Family is a family of subsets of some finite ground set whose members call be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G Such that each word ill the language is the set of arcs of some path in G, is a polynomial-time solvable problem.
机译：有向路径族是一些有限地面集的子集，其成员称为在某些有向图中的简单有向路径的弧集。在本文中，我们证明，即使给定的家庭中的所有成员最多具有两个要素，也要认识到给定的家庭是否为定向路径家庭是NP完全问题。如果不是给一个子集族，而是给我们一个有限字母的单词集合，然后确定是否存在一个有向图G，使得该语言中的每个单词都是G中某个路径的弧的集合，就是一个多项式时间可解决的问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号