Veröffentlichung

Titel:

On Solving Reachability in Grid Digraphs using a Pseudoseparator

AutorInnen:

Rahul Jain
Raghunath Tewari

Kategorie:

Artikel in Zeitschriften

erschienen in:

Theory of Computing, Vol. 19, No. 2, pp. 1-23, 2023

Abstract:

The reachability problem asks to decide if there exists a path from one vertex to another in a digraph. In a grid digraph, the vertices are the points of a two-dimensional square grid, and an edge can occur between a vertex and its immediate horizontal and vertical neighbors only. Asano and Doerr (CCCG'11) presented the first simultaneous time-space bound for reachability in grid digraphs by solving the problem in polynomial time and O(n^1/2+ϵ) space. In 2018, the space complexity was improved to Õ(n^1/3) by Ashida and Nakagawa (SoCG'18). In this paper, we show that there exists a polynomial-time algorithm that uses O(n^1/4+ϵ) space to solve the reachability problem in a grid digraph containing n vertices. We define and construct a new separator-like device called pseudoseparator to develop a divide-and-conquer algorithm. This algorithm works in a space-efficient manner to solve reachability.

Download:

Theory of Computing

BibTeX-Eintrag:

@article{v019a002, author = {Jain, Rahul and Tewari, Raghunath}, title = {On Solving Reachability in Grid Digraphs using a Pseudoseparator}, year = {2023}, pages = {1--23}, doi = {10.4086/toc.2023.v019a002}, publisher = {Theory of Computing}, journal = {Theory of Computing}, volume = {19}, number = {2}, URL = {https://theoryofcomputing.org/articles/v019a002}, }