Finite Playground

To verify is human; to prove, divine.


Leave a comment

Complexity of reachability problem on surface graphs

Directed reachability problem on surface graphs can be solved in poly-time and sub-linear space (!).  See the survey by Vinodchandran Variyam.  

Advertisements