We propose a new model for studying graph related problems that we call the \emph{orientation model}. In this model, an undirected graph $G$ is fixed, and the input is any possible edge orientation of $G$. A property is now a property of the directed graph that is obtained by a ... more >>>

One way to quantify how dense a multidag is in long paths is to find the largest n, m such that whichever ≤ n edges are removed, there is still a path from an original input to an original output with ≥ m edges - the larger we can make ... more >>>

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>