Memory-efficient enumeration of constrained spanning trees
Abbreviated Journal Title
Inf. Process. Lett.
enumeration; exhaustive search; combinatorics; optimization; algorithms; output-sensitive; graphs; spanning trees; constraints; COMPLEXITY; Computer Science, Information Systems
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.
Information Processing Letters
"Memory-efficient enumeration of constrained spanning trees" (1999). Faculty Bibliography 1990s. 2768.