Via polylogblog I learn that the list of accepted papers at STACS has become available.

Three graph algorithm titles caught my attention enough to get me to track down their online versions, though I haven't had time to do much more than scan their abstracts:

Finding Induced Subgraphs via Minimal Triangulations (arXiv:0909.5278) by Fomin and Villanger. This turns out to be about finding moderately-exponential algorithms that find subgraphs of bounded treewidth that are as large as possible and to solve subgraph isomorphism problems when the subgraph to be found is large but of bounded treewidth.

Two-phase algorithms for the parametric shortest path problem by Chakraborty, Fischer, Lachish, and Yuster. Parametric optimization problems involve an input graph with weights that vary (linearly or more complicatedly) with some parameter; one must solve an optimization problem like shortest paths for particular parameter values. In the version studied here, one doesn't want all the different shortest paths for all different parameter values (there can be superpolynomially many different paths even when the edge weights vary linearly); rather, we'd like to compute the shortest path for some small set of parameter values, more quickly than the \( O(mn) \) per value that it would take to run Bellman-Ford separately for each value. (One can't use Dijkstra because some edges may be negative.) The authors show that, with polynomial preprocessing, shortest paths for each parameter value may be found in \( O(m + n log n) \) time, as fast as Dijkstra.

Planar Subgraph Isomorphism Revisited (arXiv:0909.4692) by Dorn. This is a followup to one of my papers, which provides a completely impractical algorithm for finding any \( k \)-vertex subgraph (for fixed \( k \)) in a larger planar graph in linear time. The algorithm described here has been improved: it's now exponential in \( k \) rather than \( k \log k \). I'm still not convinced that it's at all close to practical, but it's a step in the right direction.