ISAAC 2010 acceptances

The list of accepted papers to ISAAC 2010 (in December in Korea) is online, and it also includes abstracts. I've already described the preprint versions of my two contributed papers, on flows in minor-free graphs and clique-finding, so instead I'll mention a few of the other abstracts that intrigued me:

• Senot, Durand-Lose, and Duchier report on a graphical technical for solving NP-hard SAT problems by drawing lines in the plane, which (they say) can be viewed as a kind of massively parallel algorithm.

• Farzan, Gagie, and Navarro describe data structures for storing a compressed representation of a set of points in the plane, with total space only a small amount above the entropy of the set, that can nevertheless perform many standard range querying tasks quickly.

• Limouzy introduces a new type of graph minor concept involving complementation of the edges around a vertex, shows that it preserves cographs and modular decompositions, and uses it to find a forbidden graph characterization of permutation graphs.

• Di Giacomo, Didimo, Liotta, and Meijer investigate drawings of trees that are neary Euclidean minimum spanning trees of their vertices, in the sense that each edge in the drawing is at most a small factor larger than the longest edge in the EMST path connecting the same two vertices. Although most trees cannot be drawn as exact EMSTs, all trees have nearly-EMST drawings in this sense.

• Adiga, Chitnis, and Saurabh find efficient FPT algorithms for computing the boxicity of a graph (the minimimum dimension of a representation as an intersection graph of boxes), when parametrized by vertex cover number.

There were many other interesting looking abstracts as well, so I think it should be a good conference.

Comments: