Special case of Hamiltonian cycle

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Special case of Hamiltonian cycle

Post by alex[LSD] » Sun Feb 13, 2005 9:47 am

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! :D
The more contests are held, the happier I am.

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Re: Special case of Hamiltonian cycle

Post by nnahas » Sun Feb 13, 2005 1:59 pm

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! :D
Read the first section of this paper (Proof of Ore's theorem) :
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"

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Sun Feb 13, 2005 4:01 pm

Wow! You are everywhere! Great!
Thanks for the link, if by V you mean the number of vertices, than the ALGO looks pretty much like the one everybody has used.
10k u very much!
The more contests are held, the happier I am.

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Sun Feb 13, 2005 7:18 pm

Got AC, sad that I can't come up with trics like this. :cry:
The more contests are held, the happier I am.

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Post by nnahas » Sun Feb 13, 2005 9:24 pm

alex[LSD] wrote:Got AC, sad that I can't come up with trics like this. :cry:
I don't know if that can make you feel better, but I didn't come up with it either. I just had studied the theorem (and its proof) when I was at university :)

Post Reply

Return to “Algorithms”