0
$\begingroup$

Given any undirected, connected and simple graph $G(V,E)$,each node of which is considered as a city. We call $j$ a neighbor of $i$ if $(i,j)\in E$. $N_i$ is the set of neighbors of $i$. $|V|=N$

There is a traveler who starts travelling from some city and wants to visit all cities. But he does not have a map,it means he only knows about the local information,i.e. he only knows the neighbors of a city when staying at that city. Each time, he moves to a neighbor of currently staying city.

Suppose he traveled from city a to b 3 times and b to a 2 times, then we call link (a,b) (or (b,a)) has been used totally 5 times.

I am considering an algorithm: each time, suppose he stays in some city $i$, and he selects a neighbor city of $i$ whose link between $i$ has been used least times in the past, except the city he visited at last time, and move to that city. If more than 1, any of them is OK.

I want to know for any graph $G$, after how many times, he will must visit all the cities.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What exactly is your question? A most efficient walk? An algorithm? Complexity? $\endgroup$
    – Wlodek Kuperberg
    Commented Sep 10, 2013 at 14:53
  • $\begingroup$ Deterministically we can get at most $n^2$ steps on $n$ nodes by simply remembering all vertices/edges that we have seen (not visited, but seen via the 'knows all neighbors'), and at each step picking a random unvisited vertex and walking to it. We can walk to the kth one in at most k steps, so the total number of steps is $\sum_{k=1}^{n} k = n(n+1)/2$ $\endgroup$
    – David Benson-Putnins
    Commented Sep 11, 2013 at 3:37

1 Answer 1

Reset to default
2
$\begingroup$

The 2 papers below show that the expected efficiency of the method of simply running a random walk on your graph, until the $n$ nodes are covered, ranges from $n\ln n$ steps on a nice graph like the complete one, to $\tfrac4{27}n^3$ steps on the lollipop graph, cf.:

  • U. Feige, A tight upper bound on the cover time for random walks on graphs, Random Struct Alg 6(1) (1995), 51-54.

  • U. Feige, A tight lower bound on the cover time for random walks on graphs, Random Struct Alg 6(4) (1995), 433-438.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .