A POLYNOMIAL ALGORITHM FOR THE 2-PATH PROBLEM FOR SEMICOMPLETE DIGRAPHS

作     者：BANGJENSEN, J THOMASSEN, C 

作者机构：TECH UNIV DENMARKINST MATHDK-2800 LYNGBYDENMARK 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1992年第5卷第3期

页      面：366-376页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：TOURNAMENTS SEMICOMPLETE DIGRAPHS K-PARTITE TOURNAMENTS POLYNOMIAL ALGORITHMS NP-COMPLETENESS FEEDBACK VERTEX SET FEEDBACK ARCSET 2-PATH PROBLEM 

摘      要：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 tournanment are both NP-complete.