Time-space tradeoffs for dynamic programming algorithms in trees and bounded treewidth graphs
DOI10.1007/978-3-319-21398-9_28zbMATH Open1465.68203OpenAlexW2281382292MaRDI QIDQ3196398FDOQ3196398
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
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
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)
Cited In (18)
- Improved space efficient algorithms for BFS, DFS and applications
- Execution time analysis of a top-down R-tree construction algorithm
- 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
- A framework for in-place graph algorithms
- Design of algorithms for spatial-time reduction complexity of dynamic programming
- 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
- Title not available (Why is that?)
- Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
- Approximation in (poly-) logarithmic space
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)
