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
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

User avatar
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:

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