0
$\begingroup$

Does this algorithm traverse trees (correctly) in logspace?


Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree is a connected undirected graph with N-1 edges.


Define nextNeighbor(current, previous):

If current has a neighbor larger than previous, then return the smallest such neighbor.

Otherwise, return the smallest neighbor of current.


Initialize current to the vertex you want to traverse from.

Initialize previous to the largest neighbor of current. (Assume current has at least 1 neighbor.)

Repeatedly call nextNeighbor 2*(N-1) iterations (you'll walk each of the N-1 edges twice). For each iteration, update previous to current and current to the output of nextNeighbor.


Implementation:

$\endgroup$
  • 1
    $\begingroup$ Your algorithm works in logspace. $\endgroup$ – Yuval Filmus Jun 4 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.