Antidirected Hamiltonian paths between specified vertices of a tournament (Q1348380): Difference between revisions

Let \(a\) and \(b\) be specified vertices of a tournament \(T\). The authors show that if \(T\) is sufficiently large, then \(T\) contains an antidirected Hamiltonian path from \(a\) to \(b\) in which the first arc has specified direction, provided that \(a\) and \(b\) satisfy a certain necessary condition. They use this result to give a polynomial time algorithm for finding an antidirected Hamiltonian path between two specified vertices of a tournament \(T\) or deciding that it doesn't exist.