Thore Husfeldt

Exponential Time Algorithms at SODA 2012

with 3 comments

Accepted papers for the algorithms conference SODA 2012 are announced. Best conference ever! (Compare my SODA post from last year.)

Based on my quick perusal of list of accepted papers [PDF], here’s a list of papers related to exponential time computation, together with references to online version — I’m probably missing some. Updates are welcome.

  • Counting Perfect Matchings as Fast as Ryser [ 1107.4466], by Andreas Björklund
  • Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset, by Rajesh Chitnis, Mohammadtaghi Hajiaghayi and Dániel Marx
  • Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem [arxiv 1107.3704], by Stefan Kratsch
  • Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization [ECCC 2011-072], by Danny Hermelin and Xi Wu
  • Subexponential Parameterized Algorithm for Minimum Fill-in [arxiv 1104.2230] by Fedor V. Fomin and Yngve Villanger
  • A Satisfiability Algorithm for AC0 [arxiv 1107.3127], by Russel Impagliazzo, William Matthews and Ramamohan Paturi
  • Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal [arxiv 1107.3068] by Stefan Kratsch and Magnus Wahlström
  • Fast zeta transforms for point lattices, by Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof and Pekka Parviainen
  • Shortest Cycle Through Specified Elements [PDF], by Andreas Björklund, Thore Husfeldt and Nina Taslaman
  • Kernelization of Packing Problems, by Holger Dell and Dániel Marx
  • Linear Kernels for (Connected) Dominating Set on H-minor-free graphs [PDF], by Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos
  • Bidimensionality and Geometric Graphs [arxiv 1107.2221], by Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh

An amazing number of kernelisation (and, I presume non-kernelisation) papers. And lots and lots of exciting papers in many other fields as well.


Written by thorehusfeldt

September 12, 2011 at 21:04

Posted in Conferences

3 Responses

Subscribe to comments with RSS.

  1. A Satisfiability Algorithm for AC0
    Russel Impagliazzo, William Matthews and Ramamohan Paturi


    September 12, 2011 at 21:53

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: