# Workshop Program

**Thursday, September 10, 2009**

**9:00-9:50. WAOA Invited Talk. **

*Combinatorial Algorithms for Convex Programs Capturing Market Equilibria and Nash Bargaining Solutions *

V. Vazirani

**10:00-11:15. IWPEC Session 1 (Session Chair: H. Fernau).**

*On Digraph Width Measures in Parameterized Algorithmics*

R. Ganian, P. Hlineny, J. Kneis, A. Langer, J. Obdržálek, and P. Rossmanith

*Well-Quasi-Ordering Bounded Treewidth Graphs*

M. Fellows, D. Hermelin, and F. A. Rosamond

*Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor*

S. Gutner

**11:40-12:55. IWPEC Session 2 (Session Chair: I. Razgon).**

*Partitioning into Sets of Bounded Cardinality*

M. Koivisto

*Even Faster Algorithm for Set Splitting! *

D. Lokshtanov and S. Saurabh

*What Makes Equitable Connected Partition Easy *

R. Enciso, M. Fellows, J. Guo, I. Kanj, F. Rosamond, and O. Suchý

**14:00-14:50. WAOA Invited Talk. **

*Algorithm Engineering for Route Planning in Realistic Scenarios*

D. Wagner

**15:00-16:15. IWPEC Session 3 (Session Chair: T. Husfeldt).**

*An exact algorithm for the Maximum Leaf Spanning Tree problem *

D. Raible, H. Fernau, J. Kneis, D. Kratsch, A. Langer, P. Rossmanith, and M. Liedloff

*On finding directed trees with many leaves *

J. Daligault and S. Thomasse

*On the Directed Degree-Preserving Spanning Tree Problem *

S. Sikdar, D. Lokshtanov, V. Raman, and S. Saurabh

**16:35-18:15. IWPEC Session 4 (Session Chair: J. Buss).**

*Boolean-width of graphs *

J. A. Telle, B.-M. Bui-Xuan and M. Vatshelle

*Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms *

P. Golovach and D. Thilikos

*Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms *

P. Damaschke

*Improved induced matchings in sparse graphs *

L. Kowalik, T. Walen, M. Krnc, and R. Erman

**Friday, September 11, 2009**

**9:00-9:50. IWPEC Invited Talk (Session Chair: J. Chen). **

*Kernelization: new upper and lower bound techniques *

H. Bodlaender

**10:00-11:15. IWPEC Session 5
(Session Chair: S. Saurabh).**

*Computing pathwidth faster than 2^n *

K. Suchan and Y. Villanger

*The complexity of satisfiability of small depth circuits*

C. Calabro, R. Impagliazzo, and R. Paturi

*An Exponential Time 2-Approximation Algorithm for Bandwidth *

M. Furer, S. Gaspers, and S. Kasiviswanathan

**11:40-12:55. IWPEC Session 6 (Session Chair: G. Gutin).**

*Planar Capacitated Dominating Set is W[1]-hard *

H. L. Bodlaender, D. Lokshtanov, and E. Penninkx

*Two Edge Modification Problems Without Polynomial Kernels *

S. Kratsch and M. Wahlström

*The parameterized complexity of some geometric problems in unbounded dimension *

P. Giannopoulos, C. Knauer, and G. Rote

**14:00-14:50. IWPEC Invited Talk (Session Chair: F. Fomin). **

*Color coding, balanced hashing and approximate counting *

N. Alon

**15:00-16:15. IWPEC Session 7
(Session Chair: H. Bodlaender).**

*Probabilistic Approach to Problems Parameterized Above Tight Lower Bound *

G. Gutin, E. J. Kim, S. Szeider, and A. Yeo

*Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover*

P. Damaschke

*Stable Assignment with Couples: Parameterized Complexity and Local Search *

D. Marx and I. Schlotter

**16:35-17:50. IWPEC Session 8 (Session Chair: S. Szeider).**

*Improved Parameterized Algorithms for the Kemeny Aggregation Problem *

N. Simjour

*FPT Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs *

G. Gutin, D. Karapetyan, and I. Razgon

*A faster fixed-parameter approach to drawing binary tanglegrams *

S. Böcker, F. Hüffner, A. Truss, and M. Wahlström