Memory-efficient enumeration of constrained spanning trees

    Authors

    J. Nievergelt; N. Deo;A. Marzetta

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Inf. Process. Lett.

    Keywords

    enumeration; exhaustive search; combinatorics; optimization; algorithms; output-sensitive; graphs; spanning trees; constraints; COMPLEXITY; Computer Science, Information Systems

    Abstract

    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.

    Journal Title

    Information Processing Letters

    Volume

    72

    Issue/Number

    1-2

    Publication Date

    1-1-1999

    Document Type

    Article

    Language

    English

    First Page

    47

    Last Page

    53

    WOS Identifier

    WOS:000084160100007

    ISSN

    0020-0190

    Share

    COinS