Title

Memory-Efficient Enumeration Of Constrained Spanning Trees

Keywords

Algorithms; Combinatorics; Constraints; Enumeration; Exhaustive search; Graphs; Optimization; Output-sensitive; Spanning trees

Abstract

Dozens of optimization problems involving constrained spanning trees have been proven to be NP-hard. In 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. © 1999 Published by Elsevier Science B.V. All rights reserved.

Publication Date

10-29-1999

Publication Title

Information Processing Letters

Volume

72

Issue

1-2

Number of Pages

47-53

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/s0020-0190(99)00117-9

Socpus ID

0347660815 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0347660815

This document is currently not available here.

Share

COinS