Hamilton subgraph - Programmers Heaven

Howdy, Stranger!

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


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.