News
A first meeting takes place on Friday, 21st April at 1pm, Johann von Neumann Haus (Rudower
Chaussee 25), Room 4.410.
Introduction
Traditionally, research on the design and analysis of
efficient algorithms concentrated on polynomial time
algorithms. However, for many important problems there are no
polynomial time algorithms, often not even polynomial time
approximation algorithms. So the best one can hope for are
algorithms whose running time is super-polynomial, but still
feasible at least for input instances of moderate
size. Designing such algorithms often requires new ideas and
techniques; many of these techniques have only been developed in
recent years. In this seminar, we will study a variety of
exponential algorithms for different problems, highlighting the
main techniques applied in this area.
The language of the
seminar is English.
Time and Place
The seminar takes place on 24th-25th July, Erwin Schrödinger
Zentrum (Rudower Chaussee 26), Room 1'307
References
Background literature
- G. Woeginger. Exact algorithms for NP-hard
problems: A survey.
- R. Downey, M. Fellows, U. Stege. Computational Tractability: The View From
Mars.
Papers for the talks
- B. Fuchs, W. Kern, D. Mölle, S. Richter, P. Rossmanith,
X. Wang. Dynamic Programming for Minimum
Steiner Trees. Manuscript, 2006.
- B. Chor, M. Fellows, D. Juedes. Linear
Kernels in Linear Time, or How to Save k Colors in
O(n2) Steps. WG 2004, LNCS 3353, 257-269, 2004.
- R. Niedermeier, P. Rossamanith. Upper Bounds for Vertex Cover
Further Improved. STACS 1999, LNCS 1563, 561-570, 1999.
- R. Beigel, D. Eppstein. 3-Coloring
in time O(1.3446n): a no-MIS algorithm.
Technical Report ECCC
TR95-033, 1995.
- E. Dantsin, A. Goerdt, E.A. Hirsch, R. Kannan, J. Kleinberg,
C.H. Papadimitriou, P. Raghavan, U. Schöning. A deterministic
(2-2/(k+1))n algorithm for k-SAT
based on local search. Theoretical Computer Science 289,
69-83, 2002.
- F. Fomin, K. Høie. Pathwidth of cubic
graphs and exact algorithms. Technical Report No. 298, University
of Bergen, 2005.
- F. Dehne, M. Fellows, M. Langston, F. Rosamond, K. Stevens. An O(2O(k)) FPT Algorithm
for the Undirected Feedback Vertex Set Problem. COCOON 2005, LNCS
3595, 859-869, 2005.
- B. Reed, K. Smith, A. Vetta. Finding Odd
Cycle transversals. Operations Research Letters,
32(4):299-301, 2004.
- S. Fiorini, N. Hardy, B. Reed, A. Vetta. Planar Graph Bipartization in Linear Time.
Manuscript, 2005.
Assignments
Coming soon.
