Short spanning closed walk on an unweighted undirected Graph

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Short spanning closed walk on an unweighted undirected Graph

Postby PeteP » Thu Sep 10, 2015 7:26 pm UTC

Didn't know whether I should ask in coding or here, but I suppose I only ask about an algorithm so here seemed better.

Anyway if I have an unweighted undirected simple Graph and want a spanning closed walk (start and ends at same node, visits every node at least once, can visit nodes several times. Length=number of edges. The shortest possible one is called hamilton walk I think) one Option is to find (one of) the shortest paths between all pairs of nodes, and add edges with the the length of the shortest path to make it a complete weighted graph. Then I can use some TSP algorithm on it and afterwards replace the edges with the corresponding nodes. And I have a relatively short closed walk

But going that way seems a bit weird to me, is there some better alternative? My google abilities seem to fail me.

Edit: Nvm found my confirmation https://books.google.de/books?id=WRIOJFrlZGQC&pg=PA65&lpg=PA65&dq=are+undirected+unweighted+graphs+still+tsp&source=bl&ots=os68eV7KSv&sig=RdW5-bkA76V5R4mr0sJd4sYEXcc&hl=de&sa=X&redir_esc=y#v=onepage&q=are%20undirected%20unweighted%20graphs%20still%20tsp&f=false

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Short spanning closed walk on an unweighted undirected G

Postby quintopia » Tue Oct 06, 2015 3:07 am UTC

The wikipedia article mentions a random algorithm that runs in 1.657^n: https://en.wikipedia.org/wiki/Hamiltonian_path_problem

Pretty sure that's somewhat faster than the algorithm you sketch (which, in the form of the Held-Karp algorithm, is also mentioned in the same article).


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 4 guests