Hamilton subgraph - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!


Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Hamilton subgraph

Hello all,

I have a problem to solve and I'm not able to find a solution.
I'm searching for some algorithm for finding a Hamilton subgraph in an oriented graph.
I don't want to find all subgraphs (i need only one), and it is not necessary to be the subgraph with maximum size (50% from the maximum size would be acceptable). Also, each node has maximum two edges. My problem is that I have a huge number of nodes. But I think that with all the simplifications (not maximum, maximum 2 edges for each nodes) the complexity could be reduced a lot.
If you can recommend some algorithms, sites or functions (can be for pascal, c/c++, visual C, Matlab) I would be very happy. I found many packages and sites on internet but most of them were for undirected graphs, and they can not search for subgraphs (they say: the graph is hamilton and this is the path, or: no hamilton graph -> no path).

Thank you,
Sign In or Register to comment.