Open Problem: Graph traversal in small memory
We have a graph G and a pool of k locations. Each location can hold one node of the graph. We say that an edge is evaluated if both its endpoints reside in the pool. In order to evaluate all the edges of $G$, one has to take turns and move nodes in to the pool whenever needed. The cost of an evaluation is the total number of times nodes are loaded on to the pool. The problem is find an evaluation of minimum cost. Approximation algorithms are ok.