scientific article; zbMATH DE number 7236409

DOI10.4230/LIPIcs.SoCG.2018.5zbMath1489.68180arXiv1803.07097MaRDI QIDQ5115772

Kotaro Nakagawa, Ryo Ashida

Publication date: 18 August 2020

Full work available at URL: https://arxiv.org/abs/1803.07097

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph algorithmgrid graphgraph reachabilitysublinear space algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Planar and grid graph reachability problems
• $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
• Directed Planar Reachability Is in Unambiguous Log-Space
• Undirected connectivity in log-space
• Universality considerations in VLSI circuits
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• The complexity of graph connectivity

This page was built for publication: