Deprecated: iconv_set_encoding(): Use of iconv.internal_encoding is deprecated in /var/www/ on line 28 Deprecated: iconv_set_encoding(): Use of iconv.input_encoding is deprecated in /var/www/ on line 29 Deprecated: iconv_set_encoding(): Use of iconv.output_encoding is deprecated in /var/www/ on line 30 Program
Strict Standards: Declaration of JCacheControllerView::get() should be compatible with JCacheController::get($id, $group = NULL) in /var/www/ on line 137


Program of IPEC 2012

[All regular talks of IPEC 2012, will take place at Rdeči Salon (Red Room) of Grand Hotel Union Executive]

Wednesday, September 12, 2012

Session 1. (Chair: Fedor V. Fomin)

10:30 – 10:55: Marcin Pilipczuk and Michał Pilipczuk

Finding a maximum induced degenerate subgraph faster than 2n

10:55 – 11:20: Chiranjit Chakraborty and Rahul Santhanam

Instance Compression for the Polynomial Hierarchy and Beyond

11:20 – 11:45: Ivan Bliznets and Alexander Golovnev

       A New Algorithm for Parameterized MAX-SAT

11:45 – 12:10: Hossein Jowhari.       (new)

       Efficient Communication Protocols for Deciding Edit Distance 

13:30 – 14:45: Saket Saurabh [TUTORIAL] (Chair: Dimitrios M. Thilikos)

Subexponential Parameterised Algorithms

Session 2. (Chair: Michał Pilipczuk)

15:15 – 15:40: Bruno Escoffier, Jérôme Monnot, Vangelis Paschos and Mingyu Xiao

New results on polynomial inapproximability and fixed parameter approximability of EDGE DOMINATING SET

15:40 – 16:05: Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri and Italo Zoppis

Restricted and Swap Common Superstring: a Parameterized View

16:05 – 16:30: Łukasz Kowalik

Nonblocker in H-minor free graphs: kernelization meets discharging

Session 3. (Chair: Dániel Marx)

17:00 – 17:25: Faisal Abu-Khzam and Mazen Bu Khuzam

An Improved Kernel for the Undirected Planar Feedback Vertex Set Problem

17:25 – 17:50: Petr A. Golovach, Pinar Heggernes, Dieter Kratsch and Reza Saei

An exact algorithm for Subset Feedback Vertex Set on chordal graphs

17:50 – 18:15: Cédric Bentz

A polynomial-time algorithm for planar multicuts with few source-sink pairs

Thursday, September 13, 2012

09:00 – 10:00: Dániel Marx [IPEC invited talk] (Chair: Dimitrios. Thilikos)

Randomized techniques for parameterized algorithms

Session 4. (Chair: Faisal Abu-Khzam)

10:30 – 10:55: Fedor V. Fomin, Bart Jansen and Michał Pilipczuk

Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?

10:55 – 11:20: Yijia Chen, Kord Eickmeyer and Jörg Flum

The exponential time hypothesis and the parameterized clique problem

11:20 – 11:45: Abhijin Adiga, Jasine Babu and L. Sunil Chandran

Polynomial Time and Parameterized Approximation Algorithms for Boxicity

15:00 – 16:15: Michał Pilipczuk [TUTORIAL] (Chair: Saket Saurabh)

Lower bounds for polynomial kernelization

Session 5. (Chair: Vangelis T. Paschos)

17:10 – 17:35: Petteri Kaski, Mikko Koivisto and Jesper Nederlof

Homomorphic Hashing for Sparse Coefficient Extraction

17:35 – 18:00: Sepp Hartung, Christian Komusiewicz and André Nichterlein

Parameterized Algorithmics for Finding 2-Clubs: Upper and Lower Bounds and Computational Experiments

 18:00 – 18:25: Markus Bläser and Radu Curticapean

Weighted counting of k-matchings is #W[1]-hard

19:00 – 20:00: IPEC business meeting

Friday, September 14, 2012

Session 6. (Chair: Marek Cygan)

10:30 – 10:55: Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki and Toshihiro Tano

Computing directed pathwidth in O(1.89n) time

10:55 – 11:20: James Abello, Pavel Klavík, Jan Kratochvíl and Tomáš Vyskočil

MSOL Restricted Contractibility to Planar Graphs

11:20 – 11:45: Michael Elberfeld, Christoph Stockhusen and Till Tantau

On the Space Complexity of Parameterized Problems

11:45 – 12:10: Adam Bouland, Anuj Dawar and Eryk Kopczyński

On Tractable Parameterizations of Graph Isomorphism

13:30 – 14:30: Andreas Björklund [IPEC invited talk]  (Chair: Erik Jan van Leeuwen)

The path taken for k-path

Session 7. (Chair: Andreas Björklund)

16:05 – 16:30: Petteri Kaski, Mikko Koivisto and Janne H. Korhonen

Fast Monotone Summation over Disjoint Sets

16:30 – 16:55: Christian Komusiewicz and Manuel Sorge

Finding Dense Subgraphs of Sparse Graphs

Session 8. (Chair: Erik Jan van Leeuwen)

17:25 – 17:50: Naomi Nishimura and Narges Simjour

Enumerating neighbour and closest strings

17:50 – 18:15: Jörg Flum and Moritz Müler

Some definitorial suggestions for parameterized proof complexity


Additional information