Memory-efficient enumeration of constrained spanning trees

DOI10.1016/S0020-0190(99)00117-9zbMATH Open1338.68116OpenAlexW2017107072WikidataQ126471184 ScholiaQ126471184MaRDI QIDQ294700FDOQ294700

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

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

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)

Cites Work

• The parallel search bench ZRAM and its applications
• Title not available (Why is that?)
• 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
• Complexity of spanning tree problems with leaf-dependent objectives
• Reverse search for enumeration
• Finding All Spanning Trees of Directed and Undirected Graphs
• Generating rooted triangulations without repetitions
• Minimum Diameter Spanning Trees and Related Problems
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• A good algorithm for smallest spanning trees with a degree constraint
• The complexity of the network design problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• The NP-completeness column: An ongoing guide

Cited In (6)

• Title not available (Why is that?)
• 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

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)