Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

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 >>>

Chris Calabro

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 ...
more >>>

Derrick Stolee, Chris Bourke, N. V. Vinodchandran

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 >>>

Hasan Abasi, Nader Bshouty

We develop a new algebraic technique that gives a simple randomized algorithm for the simple $k$-path problem with the same complexity $O^*(1.657^k)$ as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and ... more >>>