×

Antidirected Hamiltonian paths between specified vertices of a tournament. (English) Zbl 0996.05062

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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bampis, E.; Hell, P.; Manoussakis, Y.; Rosenfeld, M., Finding an Antidirected Hamiltonian Path Starting with a Forward Arc from a Given Vertex of a Tournament, (Deza, M.; Euler, R.; Manoussakis, Y., Lecture Notes in Computer Science, vol. 1120, Combinatorics and Computer Science (1996), Springer: Springer Berlin), 67-73
[2] E. Bampis, I. Milis, Y. Manoussakis, NC algorithms for Antidirected Hamiltonian Paths and Cycles in Tournaments, in E.W. Mayr et al. (Eds.), Lecture Notes in Computer Science, vol. 903, Graph Theoretic Concepts in Computer Science WG’94, Springer, Berlin, pp. 387-394.; E. Bampis, I. Milis, Y. Manoussakis, NC algorithms for Antidirected Hamiltonian Paths and Cycles in Tournaments, in E.W. Mayr et al. (Eds.), Lecture Notes in Computer Science, vol. 903, Graph Theoretic Concepts in Computer Science WG’94, Springer, Berlin, pp. 387-394. · Zbl 0856.05092
[3] Bang-Jensen, J.; Manoussakis, Y.; Thomassen, C., A polynomial algorithm for Hamilton connectedness in semicomplete digraphs, J. Algorithms, 13, 114-127 (1992) · Zbl 0749.68057
[4] Grünbaum, B., Antidirected Hamiltonian paths in tournaments, J. Combin. Theory B, 11, 249-257 (1971) · Zbl 0198.29304
[5] Havet, F.; Thomassé, S., Oriented hamiltonian paths in tournaments: a proof of Rosenfeld’s conjecture, J. Combin. Theory B, 78, 243-273 (2000) · Zbl 1026.05053
[6] Hell, P.; Rosenfeld, M., The complexity of finding generalized paths in tournaments, J. Algorithms, 4, 303-309 (1983) · Zbl 0532.68069
[7] Moon, J. W., Topics on Tournaments (1969), Holt, Reinhart and Winston: Holt, Reinhart and Winston New York · Zbl 0184.27704
[8] V. Petrovic, Antidirected Hamiltonian circuits in tournaments, in: Proceedings of the Fourth Yugoslav Seminar of Graph Theory, Novi Sad, 1983, pp. 259-269.; V. Petrovic, Antidirected Hamiltonian circuits in tournaments, in: Proceedings of the Fourth Yugoslav Seminar of Graph Theory, Novi Sad, 1983, pp. 259-269.
[9] Rosenfeld, M., Antidirected Hamiltonian paths in tournaments, J. Combin. Theory B, 12, 93-99 (1972) · Zbl 0229.05119
[10] Rosenfeld, M., Antidirected Hamiltonian circuits in tournaments, J. Combin. Theory B, 16, 234-242 (1974) · Zbl 0279.05111
[11] Soroker, D., Fast parallel algorithms for finding Hamilton paths and cycles in tournaments, J. Algorithms, 9, 276-286 (1988) · Zbl 0644.05036
[12] Thomason, A. G., Paths and cycles in tournaments, Trans. Amer. Math. Soc., 296, 167-180 (1986) · Zbl 0599.05026
[13] Thomassen, C., Antidirected Hamiltonian circuits and paths in tournaments, Math. Ann., 201, 231-238 (1973) · Zbl 0241.05109
[14] Thomassen, C., Hamiltonian-connected tournaments, J. Combin. Theory B, 28, 142-163 (1980) · Zbl 0435.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.