On Solving Reachability in Grid Digraphs using a Psuedoseparator
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910767269281792 |
|---|---|
| author | Jain, Rahul Tewari, Raghunath |
| author_facet | Jain, Rahul Tewari, Raghunath |
| contents | 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 $\tilde{O}(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1902_00488 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | On Solving Reachability in Grid Digraphs using a Psuedoseparator Jain, Rahul Tewari, Raghunath Computational Complexity Data Structures and Algorithms 68Q25 G.2.2 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 $\tilde{O}(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. |
| title | On Solving Reachability in Grid Digraphs using a Psuedoseparator |
| topic | Computational Complexity Data Structures and Algorithms 68Q25 G.2.2 |
| url | https://arxiv.org/abs/1902.00488 |