The Directed Subgraph Homeomorphism Problem.

机译：有向子图同胚问题。

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

The set of pattern graphs, for which the fixed directed subgraph homeomorphism problem is NP-complete is characterized. A polynomial time algorithm is given for the remaining cases. The restricted problem where the input graph is a directed acyclic graph is in polynomial time for all pattern graphs, and an algorithm is given. (Author)

著录项

作者
Fortune, S.; Hopcroft, J.; Wyllie, J.;
展开▼
作者单位

展开▼
年度 1978
页码 1-23
总页数 23
原文格式 PDF
正文语种 eng
中图分类工业技术;
关键词
Graphs; Combinatorial analysis; Patterns; Cycles; Algorithms; Polynomials; Input; Computer applications; Homeomorphisms;

机译：图;组合分析;模式;周期;算法;多项式;输入;计算机应用;同胚;

相似文献

外文文献
中文文献
专利

1. A minimization version of a directed subgraph homeomorphism problem [J] . Janina A. Brenner, Sándor P. Fekete, Jan C. van der Veen Mathematical Methods of Operations Research . 2009,第2期

机译：有向子图同胚问题的最小化版本
2. A minimization version of a directed subgraph homeomorphism problem [J] . Brenner J, Fekete S, van der Veen JC Mathematical methods of operations research . 2009,第2期

机译：有向子图同胚问题的最小化版本
3. Subgraph Homeomorphism via the Edge Addition Planarity Algorithm [J] . John M. Boyer Journal of Graph Algorithms and Applications . 2012,第2期

机译：通过边缘加法平面算法实现子图同胚
4. Efficient Algorithms for Node Disjoint Subgraph Homeomorphism Determination [C] . Yanghua Xiao, Wentao Wu, Wei Wang, Database Systems for Advanced Applications . 2008

机译：确定节点不相交子图同胚性的有效算法
5. The 2-Connected Steiner Subgraph Problem. [D] . Rais, Abdur. 1992

机译：2连通Steiner子图问题。
6. Hepatocellular carcinoma after direct-acting antivirals: an unresolved problem. Review of five cases [O] . Agnieszka Joanna Bartosiewicz, Tomasz Mikuła 2019

机译：直接作用抗病毒药物治疗后的肝细胞癌：一个尚未解决的问题。审查五宗案件
7. The directed subgraph homeomorphism problem [O] . Fortune Steven, Hopcroft John, Wyllie James 1980

机译：有向子图同胚问题

The Directed Subgraph Homeomorphism Problem.

摘要

著录项

相似文献

相关主题

期刊订阅