Homepage

Magnus Wahlström

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Building 46.1, Room 324
Stuhlsatzenhausweg 85
66123 Saarbrücken
Germany

Email: Get my email address via email
Phone: +49 681 9325 134
Fax: +49 681 9325 199

Research Interests

Current project: Randomized rounding, derandomization. Working on the DFG priority programme 1307 "Algorithm Engineering" with Benjamin Doerr, project "Algorithm Engineering for Developing Methods in Randomized Rounding".
Exact algorithms for hard problems: Satisfiability, graph problems, counting solutions...
Execution time analysis of branching algorithms (e.g. exponential upper bounds)

Publications

2009
- Sebastian Böcker, Falk Hüffner, Anke Truss and Magnus Wahlström: A faster fixed-parameter approach to drawing binary tanglegrams (IWPEC 2009). To appear; PDF.
- Stefan Kratsch, Magnus Wahlström: Two Edge Modification Problems Without Polynomial Kernels (IWPEC 2009). To appear; PS.
- Daniel Johannsen, Igor Razgon, Magnus Wahlström: Solving SAT for CNF formulas with a one-sided variable occurrence restriction. Accepted for SAT 2009. PDF.
- Magnus Wahlström: New Plain-Exponential Time Classes for Graph Homomorphism (CSR 2009). Official link, PDF.
- Benjamin Doerr, Magnus Wahlström: Randomized Rounding in the Presence of a Cardinality Constraint. ALENEX 2009 (PDF).
2008
- Magnus Wahlström: A tighter bound for counting max-weight solutions to 2SAT instances (IWPEC 2008). Official link, PDF.
2007
Algorithms, measures, and upper bounds for satisfiability and related problems, PhD Thesis (Linköping Studies in Science and Technology, PhD Dissertation no 1079). Available online through Linköping University e-press, or here as a PDF or Postscript file. The thesis is a monograph, and in addition to new presentations of old results, it contains the following otherwise unpublished new results:
- A new O(1.0984^n) time exact algorithm for Exact 3-satisfiability (X3SAT) in chapter 5.
- A new exact algorithm for 3-hitting set (3HS), also known as the minimum transversal problem for rank 3 hypergraphs, with a running time in O(p(n)*2.0755^k) with a limit k on the size of the hitting set, using polynomial space, and an exponential space speedup achieving a non-parameterized running time in O(1.6278^n), are in chapter 6. (A classical bound of O(1.6359^n) time with polynomial space is also given, but there is a problem in the proof of Lemma 58 which casts some doubt on it.)
- An algorithm for counting weighted solutions to 2SAT forumals (#2SAT), in O(1.2377^n) time, in chapter 7. (Now accepted at IWPEC 2008.)
- A small tightening of the analysis for the #3SAT algorithm of our TCS paper, now giving bound O(1.6671^n), is in chapter 8.
2005
- Magnus Wahlström: An algorithm for the SAT problem for formulae of linear length . In Algorithms - ESA 2005 (proceedings). ScienceDirect link, postscript
- Magnus Wahlström: Faster exact solving of SAT formulae with a low number of occurrences per va\ riable. In Proceedings of the Eighth International Conference on Theory and Applica\ tions of Satisfiability Testing (SAT-2005). ScienceDirect link, postscript
- Vilhelm Dahllöf, Peter Jonsson and Magnus Wahlström: Counting Models for 2SAT and 3SAT Formulae. Theoretical Computer Science, volume 332(1-3), pp. 265-291. ScienceDirect link, postscript
2004
- Magnus Wahlström: Exact algorithms for finding minimum transversals in rank-3 hypergraphs. Journal of Algorithms, Vol 51/2, pp. 107-121, May 2004. ScienceDirect link, postscript
2002
- Vilhelm Dahllöf, Peter Jonsson and Magnus Wahlström: Counting Satisfying Assignments in 2-SAT and 3-SAT. In Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON-2002), pp. 535-543, Singapore, Aug, 2002. postsc\ ript

Education

January 2002 - May 2007:
Ph. D. student in Computer Science at Linköping University, Sweden, group TCSLab. Title of thesis: see above.
September 1996 - January 2002:
Studies in Computer Science at Linköping University, Sweden
Title of Master's Thesis: An algorithm for finding minimum transversals in rank 3 hypergraphs (supervisor: Prof. Peter Jonsson).
June 1996:
High school graduation, Karolinska Skolan, Örebro