Space efficient algorithm for solving reachability using tree decomposition and separators
Authors:
- Rahul JainRJRahul Jain
- Raghunath TewariRTRaghunath Tewari
- 18 October 2023
- journal article
- research article
- Published by Elsevier in Theoretical Computer Science
- Vol. 982
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Log-Space Algorithms for Paths and Matchings in k-TreesTheory of Computing Systems, 2013
- Undirected connectivity in log-spaceJournal of the ACM, 2008
- Improved Approximation Algorithms for Minimum Weight Vertex SeparatorsSIAM Journal on Computing, 2008
- Combinatorial Optimization on Graphs of Bounded TreewidthThe Computer Journal, 2007
- Parallel Algorithms with Optimal Speedup for Bounded TreewidthSIAM Journal on Computing, 1998
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t ConnectivitySIAM Journal on Computing, 1998
- Linear time algorithms for NP-hard problems restricted to partial k-treesDiscrete Applied Mathematics, 1989
- Complexity of Finding Embeddings in a k-TreeSIAM Journal on Algebraic Discrete Methods, 1987
- A Separator Theorem for Chordal GraphsSIAM Journal on Algebraic Discrete Methods, 1984
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970