If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)

Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie

Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

How to solve Hamiltonian Path?

waitinforatrain · 2009-10-18 19:09:14

I have an unweighted undirected graph. I'm trying to determine how to find a path that visits each vertex only once, starting from a given vertex. From what I understand, this is referred to as a Hamiltonian Path yes? But I can find no algorithm that will help me find one... Any help appreciated, thanks.

18-10-2009 7:09pm

#1

waitinforatrain

Closed Accounts Posts: 267 ✭✭

Join Date: June 2009

Posts: 231

I have an unweighted undirected graph. I'm trying to determine how to find a path that visits each vertex only once, starting from a given vertex.

From what I understand, this is referred to as a Hamiltonian Path yes? But I can find no algorithm that will help me find one...

Any help appreciated, thanks.

0

Comments

#2 18-10-2009 7:47pm

Sheeps

Registered Users, Registered Users 2 Posts: 2,763 ✭✭✭

Join Date: October 2009

Posts: 2698

Brute force it. Hope your graph isn't too big.

0
#3 19-10-2009 8:06pm

Fremen

Registered Users, Registered Users 2 Posts: 2,481 ✭✭✭

Join Date: May 2006

Posts: 2356

This is an NP complete problem. The only way to deal with it is to brute force it.

0