Title: On the Complexity of the Graph Reachability Problem
Speaker: Vinodchandran Variyam, University of Nebraska-Lincoln
Date: Wednesday, April 25, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The graph reachability problem, the computational problem of deciding whether there is a path between two given vertices in a graph, is the canonical problem while studying space bounded computations. Different variations of this problem characterize various important space bounded complexity classes. In particular it is a basic fact that over directed graphs this problem completely characterizes non-deterministic logarithmic space bounded computations. Understanding the complexity of the reachability problem is a central concern of computational complexity theory.
In this talk I will present some progress we have made over the past 5 years at UNL on certain central open questions regarding the complexity of the reachability problem.