𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Finding an Oriented Hamiltonian Path in a Tournament

✍ Scribed by Frédéric Havet

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
153 KB
Volume
36
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We present an O n algorithm for finding a specified oriented path of order at Ž 2 . least n in a tournament of order n. Using this algorithm, we present an O n algorithm that finds a specified oriented path from a given vertex if one exists.

📜 SIMILAR VOLUMES

Oriented Hamiltonian Paths in Tournament
Oriented Hamiltonian Paths in Tournaments: A Proof of Rosenfeld's Conjecture
✍ Frédéric Havet; Stéphan Thomassé 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 284 KB

We prove that with three exceptions, every tournament of order n contains each oriented path of order n. The exceptions are the antidirected paths in the 3-cycle, in the regular tournament on 5 vertices, and in the Paley tournament on 7 vertices. ## 2000 Academic Press Tournaments are very rich st

Oriented Hamiltonian Cycles in Tournamen
Oriented Hamiltonian Cycles in Tournaments
✍ Frédéric Havet 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 379 KB

We prove that every tournament of order n 68 contains every oriented Hamiltonian cycle except possibly the directed one when the tournament is reducible.

On the Approximation of Finding A(nother
On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
✍ Cristina Bazgan; Miklos Santha; Zsolt Tuza 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 144 KB

It is a simple fact that cubic Hamiltonian graphs have at least two Hamiltonian cycles. Finding such a cycle is NP-hard in general, and no polynomial-time algorithm is known for the problem of finding a second Hamiltonian cycle when one such cycle is given as part of the input. We investigate the co

Solution of a conjecture of Volkmann on
Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in-tournaments
✍ Dirk Meierling 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

## Abstract An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. Let __m__ = 4 or __m__ = 5 and let __D__ be a strongly connected in‐tournament of order ${{n}}\geq {{2}}{{m}}-{{2}}$ such that each arc belongs to a directed path of order at