Time-space tradeoffs for dynamic programming algorithms in trees and bounded treewidth graphs

DOI10.1007/978-3-319-21398-9_28MaRDI QIDQ3196398zbMATH OpenOpenAlexFDO

Authors Niranka Banerjee, Sankardeep Chakraborty, Venkatesh Raman, Sasanka Roy, Saket Saurabh

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21398-9_28

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Recommendations

• On space efficiency of algorithms working on structural decompositions of graphs
• On space efficiency of algorithms working on structural decompositions of graphs
• scientific article; zbMATH DE number 4060712
• scientific article; zbMATH DE number 2149351
• Space saving by dynamic algebraization based on tree-depth

Cited in

(18)

• Approximation in (poly-) logarithmic space
• Execution time analysis of a top-down R-tree construction algorithm
• Improved space efficient algorithms for BFS, DFS and applications
• Width, depth, and space: tradeoffs between branching and dynamic programming
• Frameworks for designing in-place graph algorithms
• Positive-instance driven dynamic programming for treewidth
• Experimental study of compressed stack algorithms in limited memory environments
• Space-efficient vertex separators for treewidth
• Design of algorithms for spatial-time reduction complexity of dynamic programming
• A framework for in-place graph algorithms
• On space efficiency of algorithms working on structural decompositions of graphs
• On space efficiency of algorithms working on structural decompositions of graphs
• A Sub-quadratic Time and Space Complexity Solution for the Dated Tree Reconciliation Problem for Select Tree Topologies
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Forward bounding on pseudo-trees for DCOPs and ADCOPs
• Space efficient linear time algorithms for BFS, DFS and applications
• scientific article; zbMATH DE number 2149351 (Why is no real title available?)
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS

This page was built for publication: Time-space tradeoffs for dynamic programming algorithms in trees and bounded treewidth graphs

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