A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
复制标题
半完备有向图2路径问题的多项式算法
DOI：
--
复制
发表时间：
1992
影响因子：
0.8
通讯作者：
C. Thomassen
中科院分区：
文献类型：
--
作者：
J. Bang;C. Thomassen
本文给出了求半完全有向图中任意两条指定弧的圈和求完全k部定向图中任意两个指定顶点的圈的多项式有界算法。同时证明了求竞赛图的最大传递子竞赛图问题和求竞赛图中通过指定弧集的圈问题都是NP-完全的。
This paper presents polynomially bounded algorithms for finding a cycle through any two prescribed arcs in a semicomplete digraph and for finding a cycle through any two prescribed vertices in a complete k-partite oriented graph. It is also shown that the problem of finding a maximum transitive subtournament of a tournament and the problem of finding a cycle through a prescribed arc set in a tournament are both NP-complete.