Monthly Archives: April 2011

Exponential Time Algorithms at ICALP 2011

The accepted papers for ICALP 2011 have been announced.

Based on my quick perusal of the track A papers with abstracts, here’s a list of papers related to exponential time computation, together with references to online version — I’m probably missing some.

  • Isolde Adler, Stavros Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos. Tight Bounds for Linkages in Planar Graphs. PDF at Adler’s web page.
  • Sanjeev Arora and Rong Ge. New Algorithms for Learning in Presence of Errors. PDF at Ge’s web page
  • Hans L. Bodlaender, Bart M. P. Jansen and Stefan Kratsch. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. arxiv:1104.4217.
  • Andrei Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size.
  • Amin Coja-Oghlan and Angelica Pachon-Pinzon. The decimation process in random k-SAT. arxiv:1102.3145
  • Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk. Subset Feedback Vertex Set is Fixed Parameter Tractable. arxiv:1004.2972.
  • Daniel Lokshtanov and Dániel Marx. Clustering with Local Restrictions. PDF at Lokshtanov’s web page.
  • Danny Hermelin, Matthias Mnich, Erik Jan Van Leeuwen and Gerhard J. Woeginger. Domination when the Stars Are Out. arxiv:1012.0012

Unfortunately, nothing about ETH. That would have been fun.