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 $\epsilon >0$, there exists a polynomial time and $O(n^{\frac{1}{2}+\epsilon })$ space algorithm that computes the…