Title

Memory-efficient enumeration of constrained spanning trees

Authors

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