Explanation for the static degree sort algorithm of Deo et al.

Question

I would like to apply the static degree sort method of Deo et al (see section 3.1 in https://www.researchgate.net/profile/Mukkai_Krishnamoorthy/publication/220492840_Algorithms_for_Generating_Fundamental_Cycles_in_a_Graph/links/09e4150d0619a2b4bc000000.pdf). Could you please explain using the attached graph or give a pseudocode for the problem?

Answer 1

I'm not sure what part of the algorithm is confusing, so I will just break it down in steps. We are trying to construct a special kind of spanning tree.

1. First take one of the vertices with highest degree (if there are more than one to choose from, just pick one); so take vertex 1.
2. For the next vertex, choose the highest degree neighbor of the oldest vertex. So we look at our oldest vertex (vertex 1) and choose one of it's highest degree neighbors, so vertex 2 works. So now we have vertex 1 and 2 connected.
3. We are just repeating the previous step until we have added in all the vertices: we put in 4 (attached to 1), 5 (attached to 1), then 0 (attached to 1).
4. Then we have chosen all of 1s neighbors so we move on to the second oldest which is 2: so we put in 6 (attached to 2) and 3 (attached to 2).
5. The next oldest is 4, but we have already used all of its neighbors. Then 5, but we have also used all of 5s neighbors. Next is 0, but we have used all of 0s neighbors. The next is 6, which has exactly one neighbor we haven't used yet so we add 7 connected to 6.

This gives us a spanning tree, the edges are (in the order given by the algorithm) $$\{1,2\}, \{1,4\}, \{1,5\}, \{1,0\}, \{2,6\}, \{2,3\}, \{6,7\}. $$