Space-efficient algorithms for reachability in directed geometric graphs
From MaRDI portal
Publication:6039899
DOI10.1016/j.tcs.2023.113938arXiv2101.05235OpenAlexW3217069028MaRDI QIDQ6039899
Publication date: 23 May 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2101.05235
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Planar and grid graph reachability problems
- On rigid circuit graphs
- Separator theorems and Turán-type results for planar intersection graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Symmetric space-bounded computation
- Unit disk graphs
- On the power of unambiguity in log-space
- The balanced connected subgraph problem for geometric intersection graphs
- Space efficient linear time algorithms for BFS, DFS and applications
- Incidence matrices and interval graphs
- Relationships between nondeterministic and deterministic tape complexities
- Triangulated graphs and the elimination process
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Halving Balls in Deterministic Linear Time
- $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
- Depth-First Search Using $$O(n)$$ Bits
- New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.
- A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- A Separator Theorem for Chordal Graphs
- Undirected connectivity in log-space
- A Separator Theorem for Planar Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- An O ( n ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
- Compressed Decision Problems in Hyperbolic Groups.
- The complexity of graph connectivity
- Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
- Embedding and canonizing graphs of bounded genus in logspace
- Computational Complexity
- Balanced line separators of unit disk graphs
This page was built for publication: Space-efficient algorithms for reachability in directed geometric graphs
