Memory-efficient enumeration of constrained spanning trees

DOI10.1016/S0020-0190(99)00117-9zbMath1338.68116OpenAlexW2017107072WikidataQ126471184 ScholiaQ126471184MaRDI QIDQ294700

Narsingh Deo, Jurg Nievergelt, 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

combinatoricsoptimizationalgorithmsenumerationgraphsconstraintsspanning treesexhaustive searchoutput-sensitive

Mathematics Subject Classification ID

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

Related Items

Reverse search for monomial ideals

Uses Software

• ZRAM

Cites Work

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