Re: walks in graphs

From: B Loggins (breckinloggins_at_gmail.com)
Date: 12/31/04 

Date: 31 Dec 2004 15:42:25 -0800

bmoore822@hotmail.com wrote:
> Is there a special term for a closed walk in a graph that visits each
> node?
>
> Is there an algorithm for finding the smallest such walk?

The term you're looking for is a "Hamiltonian Circuit". It is defined
as a closed path through a graph that visits each node at least once.

Attempting to find an algorithm that discovers that smallest such walk
is called the "Travelling Salesman Problem;" it is NP-Complete.

For more, loop up the above terms at http://mathworld.wolfram.com.
Hope this helps.

Breckin

Relevant Pages

  • walks in graphs
    ... Is there a special term for a closed walk in a graph that visits each ... Is there an algorithm for finding the smallest such walk? ...
    (sci.math)
  • Re: Standard graph API?
    ... isomorphism graph library. ... It's pretty uniformly agreed that there is no standard graph ... the algorithm can't be specialized for the graph at ... My thought is to use some sort of templating system. ...
    (comp.lang.python)
  • Difference between two systems of DAGs
    ... I am looking for a graph algorithm, ... carry no label or other information except direction. ... edit operations are to change the label of a vertex or the ...
    (comp.theory)
  • Re: Vertex Cover implementation
    ... i code this simple greedy algorithm for the vertex cover: ... As you are constructing your graph you can update the vertex ... each edge appears on two adjacency lists. ... reason to use a priority queue for your algorithm. ...
    (comp.theory)
  • Re: combinatorial optimization problem (six-pick wager grouping)
    ... versed in graph theoretic approaches could comment on my ideas below - ... I'n not a graph theorist, nor a graph algorithm buff, so I can't really ... attempt to merge it with each bet already in the pool. ... million edges when I ignored wager size. ...
    (comp.programming)