Memory-efficient enumeration of constrained spanning trees

DOI10.1016/S0020-0190(99)00117-9MaRDI QIDQ294700zbMATH OpenOpenAlexWikidataFDO

Authors Jurg Nievergelt, Narsingh Deo, Ambros Marzetta

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019099001179?np=y

zbMATH Keywords

optimizationalgorithmsspanning treesgraphscombinatoricsconstraintsenumerationexhaustive searchoutput-sensitive

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An algorithm for the enumeration of spanning trees
• scientific article; zbMATH DE number 1086911
• Spanning Trees and Optimization Problems
• scientific article; zbMATH DE number 56828
• Enumerating Constrained Non-crossing Geometric Spanning Trees

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1086911 (Why is no real title available?)
• scientific article; zbMATH DE number 742890 (Why is no real title available?)
• A good algorithm for smallest spanning trees with a degree constraint
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• A short note on the approximability of the maximum leaves spanning tree problem
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Complexity of spanning tree problems with leaf-dependent objectives
• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• Finding All Spanning Trees of Directed and Undirected Graphs
• Generating rooted triangulations without repetitions
• Minimum Diameter Spanning Trees and Related Problems
• Reverse search for enumeration
• The NP-completeness column: An ongoing guide
• The complexity of the network design problem
• The parallel search bench ZRAM and its applications

Cited in

(6)

• scientific article; zbMATH DE number 2079850 (Why is no real title available?)
• Reverse search for monomial ideals
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
• Complexity of computation of a spanning tree enumeration algorithm
• Faster enumeration of all spanning trees of a directed graph
• Enumerating Constrained Non-crossing Geometric Spanning Trees

Describes a project that uses

Uses Software

• ZRAM

This page was built for publication: Memory-efficient enumeration of constrained spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294700)