Memory-efficient enumeration of constrained spanning trees
Dozens of optimization problems involving constrained spanning trees have been proven to be NP-hard. Ln practice, this implies that they can only be solved by exhaustive search. We show that many corresponding enumeration problems, i.e., the systematic listing of all instances of a class of constrained trees, are solved efficiently in the following sense: their state spaces exhibit a sufficiently rich structure to enable a reverse search depth-first traversal that needs neither a stack nor markers. We present and implement algorithms for various classes of "fat" and "skinny" trees. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
enumeration spanning trees optimization exhaustive search algorithms combinatorics output-sensitive graphs constraints