Raghunath Tewari

activity

20102025

most citedOn the Power of Unambiguity in Logspace

5 citations · 8 across the 10 of their papers we have counts for

collaborators

Showing 2015Show all

2 papers · 1 filter

cs.CC2015★ 1 cited

Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs

Diptarka Chakraborty, Raghunath Tewari

In this paper, we show that given a weighted, directed planar graph $G$ , and any $ε > 0$ , there exists a polynomial time and $O (n^{\frac{1}{2} + ε})$ space algorithm that computes the…

cs.DS2015

An $O (n^{ε})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Diptarka Chakraborty, Raghunath Tewari

Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$ . We show that reachabil…

Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs

An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

An $O (n^{ε})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs