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