Space efficient algorithm for solving reachability using tree decomposition and separators

DOI10.1016/j.tcs.2023.114251OpenAlexW4387745548MaRDI QIDQ6199388

Raghunath Tewari, Rahul Jain

Publication date: 23 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114251

zbMATH Keywords

tree decompositiongraph reachabilitysimultaneous time-space upper bound

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Log-space algorithms for paths and matchings in \(k\)-trees
• Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Relationships between nondeterministic and deterministic tape complexities
• $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
• New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.
• A Separator Theorem for Chordal Graphs
• Undirected connectivity in log-space
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Complexity of Finding Embeddings in a k-Tree
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• An O ( n ^ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• Embedding and canonizing graphs of bounded genus in logspace
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Parameterized Algorithms
• Space-efficient algorithms for reachability in directed geometric graphs