I need help with:
http://acm.sgu.ru/problem.php?contest=0&problem=122
If you don't want to open it, the problem is:
You have an undirected graph with N vertices. Each vertex has at least (N+1)/2 neighbours. Needed is to construct a hamiltonian cycle. I guess it is assumed that it always exists.
I heard people talk about some vertex merging technique, but I just couldn't come up with it. Too old and too dumb maybe. HEEEEELP!
Special case of Hamiltonian cycle
Moderator: Board moderators

 Learning poster
 Posts: 53
 Joined: Sat Jan 24, 2004 9:22 pm
 Location: Tomsk, Siberia, RUSSIA
 Contact:
Special case of Hamiltonian cycle
The more contests are held, the happier I am.
Re: Special case of Hamiltonian cycle
Read the first section of this paper (Proof of Ore's theorem) :alex[LSD] wrote:I need help with:
http://acm.sgu.ru/problem.php?contest=0&problem=122
If you don't want to open it, the problem is:
You have an undirected graph with N vertices. Each vertex has at least (N+1)/2 neighbours. Needed is to construct a hamiltonian cycle. I guess it is assumed that it always exists.
I heard people talk about some vertex merging technique, but I just couldn't come up with it. Too old and too dumb maybe. HEEEEELP!
http://www.ecp6.jussieu.fr/pageperso/ bondy/research/papers/shortproofs.ps
The proof implicitly gives an algorithm (O(V^2) if I am not mistaken) . Also there is a typo in the proof, so replace every occurence of "S+" with "S"