I am given an undirected graph. Initially all vertices are white. I need to color them black in such an order that the maximum number of vertices which are on the border between black and white regions is minimal. Is there an algorithm to find an optimal order for that?

More formally. We are given an undirected, connected graph $ G = (V,E)$ consisting of $ n$ vertices. I am looking for a sequence of increasing subsets of vertices $ V_0, V_1, …, V_n$ , where $ V_0 = \emptyset$ , $ V_{i+1} = V_i \cup \{v\}$ for some $ v\in V$ , and $ V_n = V$ . For any subset $ W \subset V$ we define a cost function $ c(W)$ as the number of “border” vertices, i.e. size of $ \{w\in W : \exists m\in V\setminus W: (w,m)\in E \}$ . I am looking for such a sequence where $ \max_i(c(V_i))$ is minimal.

I feel my problem is somehow related to maximum flow algorithms, the same way as minimum-cut problem is. I think there must be a name for this (or similar) problem. However, as I was mixing “minimal cut” in various ways in the search engines, I was unable to find it.

A bit of context: I have a series of tasks to perform (edges), each loading two files from a disk (vertices). In order to speed up the process, I don’t want the reload every pair of files every time. Instead, I want to keep some files in memory so that I can reuse them when another task uses the same file. But I cannot keep all files that there are because of memory constriants. The above sequence would help me select an optimal processing order, keeping the number of active files to minimum.