An improved N-tree algorithm for the enumeration of all neighbors of a degenerate vertex

Based on the concept of degeneracy graphs, theoretical and algorithmic aspects of the neighborhood-problem are dealt with. It is shown that any subgraph of a positive degeneracy graph which is induced by a set of nodes feasible with respect to an arbitrary lexicographic pivot selection will supply sufficient information. A special lexicographic pivot selection strategy is presented which leads to an improved version of the N-tree method. The increase in efficiency is illustrated by test results.