×

zbMATH — the first resource for mathematics

A polynomial algorithm for the 2-path problem for semicomplete digraphs. (English) Zbl 0759.05041
Authors’ summary: 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.
Reviewer: G.Chaty (Paris)

MSC:
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C40 Connectivity
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI