Dr Magnus Wahlström

  1. 2018
  2. Forthcoming

    Multi-budgeted directed cuts

    Kratsch, S., Li, S., Marx, D., Pilipczuk, M. & Wahlstrom, M. 29 Jun 2018 IPEC 2018. (Leibniz International Proceedings in Informatics (LIPIcs))

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. Published

    Directed Multicut is W[1]-hard, Even for Four Terminal Pairs

    Pilipczuk, M. & Wahlstrom, M. 23 May 2018 In : ACM Transactions on Computation Theory (TOCT). 10, 3, 18 p., 13

    Research output: Contribution to journalArticle

  4. E-pub ahead of print

    Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials

    Gutin, G., Reidl, F., Wahlstrom, M. & Zehavi, M. 30 Apr 2018 In : Journal of Computer and System Sciences. 95, p. 69-85

    Research output: Contribution to journalArticle

  5. E-pub ahead of print

    k-distinct in- and out-branchings in digraphs

    Gutin, G., Reidl, F. & Wahlstrom, M. 7 Mar 2018 In : Journal of Computer and System Sciences. 95, p. 86-97

    Research output: Contribution to journalArticle

  6. Published

    Parameterized Algorithms for Zero Extension and Metric Labelling Problems

    Reidl, F. & Wahlstrom, M. 2018 ICALP 2018 Track A. (Leibniz International Proceedings in Informatics )

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  7. 2017
  8. Published

    Path-contractions, edge deletions and connectivity preservation

    Gutin, G., Ramanujan, M. S., Reidl, F. & Wahlstrom, M. 3 Sep 2017 The 25th Annual European Symposium on Algorithms (ESA 2017). p. 1-13 13 p. (LIPICS; vol. 87)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  9. Published

    Kernelization of Constraint Satisfaction Problems: A Study through Universal Algebra

    Lagerkvist, V. & Wahlstrom, M. 23 Aug 2017 Principles and Practice of Constraint Programming: 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 – September 1, 2017, Proceedings. Springer, p. 157-171 15 p. (Lecture Notes in Computer Science; vol. 10416)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  10. Published

    Odd Properly Colored Cycles in Edge-Colored Graphs

    Gutin, G., Sheng, B. & Wahlstrom, M. 1 Apr 2017 In : Discrete Mathematics. 340, 4, p. 817–821 5 p.

    Research output: Contribution to journalArticle

  11. Published

    Acyclicity in Edge-Colored Graphs

    Gutin, G., Jones, M., Sheng, B., Wahlstrom, M. & Yeo, A. 6 Feb 2017 In : Discrete Mathematics. 340, 2, p. 1-8 8 p.

    Research output: Contribution to journalArticle

  12. Published

    Rural Postman Parameterized by the Number of Components of Required Edges

    Gutin, G., Wahlström, M. & Yeo, A. 1 Feb 2017 In : Journal of Computer and System Sciences. 83, 1, p. 121-131 11 p.

    Research output: Contribution to journalArticle

  13. Published

    Chinese Postman Problem on Edge­-Colored Multigraphs

    Gutin, G., Jones, M., Sheng, B., Wahlstrom, M. & Yeo, A. 30 Jan 2017 In : Discrete Applied Mathematics. 217, p. 196-202 7 p.

    Research output: Contribution to journalArticle

  14. Published

    k-Distinct In- and Out-Branchings in Digraphs

    Gutin, G., Reidl, F. & Wahlstrom, M. 2017 44th International Colloquium on Automata, Languages, and Programming: ICALP 2017. Dagstuhl, p. 1-13 13 p. (Leibniz International Proceedings in Informatics ; vol. 80)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  15. Published

    LP-branching algorithms based on biased graphs

    Wahlström, M. 2017 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Vol. PRDA17, p. 1559-1570 12 p. (Proceedings)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  16. Published

    Parameterized Complexity of the Workflow Satisfiability Problem

    Cohen, D., Crampton, J., Gutin, Z. & Wahlstrom, M. 2017 Combinatorial Optimization and Graph Algorithms. Springer-Verlag

    Research output: Chapter in Book/Report/Conference proceedingChapter

  17. 2016
  18. Published

    On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations

    Crampton, J., Gagarin, A., Gutin, G., Jones, M. & Wahlstrom, M. 1 Dec 2016 In : ACM Transactions on Privacy and Security. 19, 3, p. 1-29 29 p.

    Research output: Contribution to journalArticle

  19. Published

    The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth

    Gutin, G., Jones, M. & Wahlstrom, M. 29 Nov 2016 In : SIAM Journal on Discrete Mathematics. 30, 4, p. 2177-2205 29 p.

    Research output: Contribution to journalArticle

  20. Published

    How to Generate Randomized Roundings with Dependencies and How to Derandomize Them

    Doerr, B. & Wahlström, M. 11 Nov 2016 Algorithm Engineering: Selected Results and Surveys. Springer, Vol. 9220, p. 159-184 26 p. (Lecture Notes in Computer Science; vol. 9220)

    Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

  21. Published

    Half-integrality, LP-branching and FPT algorithms

    Iwata, Y., Wahlstrom, M. & Yoshida, Y. 9 Aug 2016 In : SIAM Journal on Computing. 45, 4, p. 1377–1411 35 p.

    Research output: Contribution to journalArticle

  22. Published

    On problems as hard as CNF-SAT

    Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S. & Wahlström, M. 1 Jun 2016 In : ACM Transactions on Algorithms (TALG). 12, 3, 41

    Research output: Contribution to journalArticle

  23. Published

    The power of primitive positive definitions with polynomially many variables

    Lagerkvist, V. & Wahlstrom, M. 19 Mar 2016 In : Journal of Logic and Computation. p. 1-21 21 p.

    Research output: Contribution to journalArticle

  24. Published

    Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis

    Gutin, G. & Wahlstrom, M. Mar 2016 In : Information Processing Letters. 116, 3, p. 223-226 4 p.

    Research output: Contribution to journalArticle

  25. Published

    Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

    Kratsch, S., Marx, D. & Wahlstrom, M. 3 Feb 2016 In : ACM Transactions on Computation Theory (TOCT). 8, 1, p. 1-28 28 p.

    Research output: Contribution to journalArticle

  26. Published

    Directed multicut is W[1]-hard, even for four terminal pairs

    Pilipczuk, M. & Wahlstrom, M. 2016 Proceedings of SODA 2016. Krauthgamer, R. (ed.). SIAM, p. 1167-1178 12 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  27. 2015
  28. Published

    A Completeness Theory for Polynomial (Turing) Kernelization

    Hermelin, D., Kratsch, S., Soltys, K., Wahlström, M. & Wu, X. 1 Mar 2015 In : Algorithmica. 71, 3, p. 702-730 29 p.

    Research output: Contribution to journalArticle

  29. Published

    Fixed-parameter tractability of multicut in directed acyclic graphs

    Kratsch, S., Pilipczuk, M., Pilipczuk, M. & Wahlström, M. 2015 In : SIAM Journal on Discrete Mathematics. 29, 1, p. 122-144 23 p.

    Research output: Contribution to journalArticle

  30. Published

    Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

    Gutin, G., Kratsch, S. & Wahlström, M. 2015 In : Algorithmica. p. 1-20 20 p.

    Research output: Contribution to journalArticle

  31. Published

    Structural Parameterizations of the Mixed Chinese Postman Problem

    Gutin, G., Jones, M. & Wahlstrom, M. 2015 23rd Europ. Symp. Algorithms (ESA 2015). Springer-Verlag, Vol. 9294, p. 668-679 (Lect. Notes Comput. Sci.)

    Research output: Chapter in Book/Report/Conference proceedingChapter

  32. 2014
  33. Published

    Randomized Rounding in the Presence of a Cardinality Constraint

    Doerr, B. & Wahlström, M. 1 Sep 2014 In : ACM Journal of Experimental Algorithmics. 19, 2

    Research output: Contribution to journalArticle

  34. Published

    Calculation of Discrepancy Measures and Applications

    Doerr, C., Gnewuch, M. & Wahlström, M. 2014 A Panorama of Discrepancy Theory. Springer, (Lecture Notes in Mathematics; vol. 2107)

    Research output: Chapter in Book/Report/Conference proceedingChapter

  35. Forthcoming

    Clique cover and graph separation: New incompressibility results

    Cygan, M., Kratsch, S., Pilipczuk, M., Pilipczuk, M. & Wahlström, M. 2014 In : ACM Transactions on Computation Theory (TOCT). 6, 2

    Research output: Contribution to journalArticle

  36. Forthcoming

    Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal

    Kratsch, S. & Wahlström, M. 2014 In : ACM Transactions on Algorithms (TALG). 10, 4, 20 p.

    Research output: Contribution to journalArticle

  37. Published

    Half-integrality, LP-branching and FPT Algorithms

    Wahlström, M. 2014 SODA. Chekuri, C. (ed.). SIAM, p. 1762-1781 20 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  38. Published

    Kernelization, Matroid Methods

    Wahlström, M. 2014 Encyclopedia of Algorithms. Springer, p. 1-6 6 p.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  39. Published

    Parameterized Directed k-Chinese Postman Problem and k Arc-Disjoint Cycles Problem on Euler Digraphs

    Gutin, G., Jones, M., Sheng, B. & Wahlström, M. 2014 Proceedings of WG 2014.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  40. Published

    Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

    Gutin, G., Kratsch, S. & Wahlström, M. 2014 Proceedings of IPEC 2014.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  41. Published

    Polynomially Closed Co-clones

    Lagerkvist, V. & Wahlström, M. 2014 Proceedings of ISMVL 2014: IEEE 44th International Symposium on Multiple-Valued Logic. IEEE, p. 85-90 6 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  42. 2013
  43. Published

    A Completeness Theory for Polynomial (Turing) Kernelization

    Hermelin, D., Kratsch, S., Soltys, K., Wahlström, M. & Wu, X. 2013 IPEC. Springer, Vol. LNCS 8246, p. 202 215 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  44. Published

    Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem

    Wahlström, M. 2013 STACS. p. 341-352 12 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  45. Published

    Parameterized Two-Player Nash Equilibrium

    Hermelin, D., Huang, C-C., Kratsch, S. & Wahlström, M. 2013 In : Algorithmica. 65, 4, p. 802-816 15 p.

    Research output: Contribution to journalArticle

  46. Published

    Two Edge Modification Problems Without Polynomial Kernels

    Kratsch, S. & Wahlström, M. 2013 In : Discrete Optimization. 10, p. 193-199

    Research output: Contribution to journalArticle

  47. 2012
  48. Published

    A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting

    Gnewuch, M., Wahlström, M. & Winzen, C. 2012 In : SIAM Journal on Numerical Analysis. 50, 2, p. 781-807 27 p.

    Research output: Contribution to journalArticle

  49. Published

    Clique Cover and Graph Separation: New Incompressibility Results

    Cygan, M., Kratsch, S., Pilipczuk, M., Pilipczuk, M. & Wahlström, M. 2012 ICALP (1). p. 254-265 12 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  50. Published

    Compression via matroids: a randomized polynomial kernel for odd cycle transversal

    Kratsch, S. & Wahlström, M. 2012 SODA. p. 94-103 10 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  51. Published

    Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs

    Kratsch, S., Pilipczuk, M., Pilipczuk, M. & Wahlström, M. 2012 ICALP (1). p. 581-593 13 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  52. Published

    Hardness of discrepancy computation and epsilon-net verification in high dimension

    Giannopoulos, P., Knauer, C., Wahlström, M. & Werner, D. 2012 In : Journal of Complexity. 28, 2, p. 162-176 15 p.

    Research output: Contribution to journalArticle

  53. Published

    On Problems as Hard as CNF-SAT

    Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S. & Wahlström, M. 2012 IEEE Conference on Computational Complexity. p. 74-84 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  54. Published

    Representative sets and irrelevant vertices: New tools for kernelization

    Kratsch, S. & Wahlström, M. 2012 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 450-459 10 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  55. Published

    Subexponential Parameterized Odd Cycle Transversal on Planar Graphs

    Lokshtanov, D., Saurabh, S. & Wahlström, M. 2012 FSTTCS.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  56. 2011
  57. Published

    Dependent Randomized Rounding: The Bipartite Case

    Doerr, B., Künnemann, M. & Wahlström, M. 2011 2011 Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Müller-Hannemann, M. & Werneck, R. (eds.). San Francisco, California, USA: SIAM, p. 96-106 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  58. Unpublished

    Hierarchies of Inefficient Kernelizability

    Hermelin, D., Kratsch, S., Soltys, K., Wahlström, M. & Wu, X. 2011 In : ArXiv.org. CoRR:abs/1110.0976

    Research output: Contribution to journalArticle

  59. Published

    New Plain-Exponential Time Classes for Graph Homomorphism

    Wahlström, M. 2011 In : Theory of Computing Systems. 49, 2, p. 273-282 10 p.

    Research output: Contribution to journalArticle

  60. Published

    Parameterized Two-Player Nash Equilibrium

    Hermelin, D., Huang, C-C., Kratsch, S. & Wahlström, M. 2011 Graph-Theoretic Concepts in Computer Science : 37th International Workshop, WG 2011. Kolman, P. & Kratochvíl, J. (eds.). Teplá Monastery, Czech Republic: Springer, Vol. 6986, p. 215-226 12 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  61. 2010
  62. Published

    Algorithmic construction of low-discrepancy point sets via dependent randomized rounding

    Doerr, B., Gnewuch, M. & Wahlström, M. 2010 In : Journal of Complexity. 26, 5, p. 490-507 18 p.

    Research output: Contribution to journalArticle

  63. Published

    Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

    Kratsch, S., Marx, D. & Wahlström, M. 2010 Mathematical Foundations of Computer Science 2010 : 35th International Symposium, MFCS 2010. Hlinený, P. & Kucera, A. (eds.). Brno, Czech Republic: Springer, Vol. 6281, p. 489-500 12 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  64. Published

    Preprocessing of Min Ones Problems: A Dichotomy

    Kratsch, S. & Wahlström, M. 2010 Automata, Languages and Programming : 37th International Colloquium, ICALP 2010. Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F. & Spirakis, P. G. (eds.). Bordeaux, France: Springer, Vol. 6198, p. 653-665 13 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  65. Published

    Randomized Rounding for Routing and Covering Problems: Experiments and Improvements

    Doerr, B., Künnemann, M. & Wahlström, M. 2010 Experimental Algorithms : 9th International Symposium, SEA 2010. Festa, P. (ed.). Naples, Italy: Springer, Vol. 6049, p. 190-201 12 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  66. 2009
  67. Published

    Two Edge Modification Problems without Polynomial Kernels

    Kratsch, S. & Wahlström, M. 1 Sep 2009 Parameterized and Exact Computation : 4th International Workshop, IWPEC 2009. Chen, J. & Fomin, F. V. (eds.). Denmark, Copenhagen: Springer, Vol. 5917, p. 264-275 12 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  68. Published

    Implementation of a component-by-component algorithm to generate small low-discrepancy samples

    Doerr, B., Gnewuch, M. & Wahlström, M. 1 Jul 2009 Monte Carlo and Quasi-Monte Carlo Methods 2008. L'Ecuyer, P. & Owen, A. B. (eds.). Montreal, Canada: Springer, p. 323-338 16 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  69. Published

    A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams

    Böcker, S., Hüffner, F., Truss, A. & Wahlström, M. 2009 Parameterized and Exact Computation : 4th International Workshop, IWPEC 2009. Chen, J. & Fomin, F. V. (eds.). Copenhagen, Denmark: Springer, Vol. 5917, p. 38-49 12 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  70. Published

    BBOB: Nelder-Mead with resize and halfruns

    Doerr, B., Fouz, M., Schmidt, M. & Wahlström, M. 2009 Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (GECCO 2009). Rothlauf, F. (ed.). Montreal, Québec, Canada: ACM, p. 2239-2246 8 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  71. Published

    New Plain-Exponential Time Classes for Graph Homomorphism

    Wahlström, M. 2009 Computer Science - Theory and Applications : 4th International Computer Science Symposium in Russia, CSR 2009. Frid, A., Morozov, A., Rybalchenko, A. & Wagner, K. W. (eds.). Novosibirsk, Russia: Springer, Vol. 5675, p. 346-355 10 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  72. Published

    Randomized Rounding in the Presence of a Cardinality Constraint

    Doerr, B. & Wahlström, M. 2009 2009 Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX). Finocchi, I. & Hershberger, J. (eds.). New York, USA: SIAM, p. 162-174 13 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  73. Published

    Solving SAT for CNF formulas with a one-sided variable occurrence restriction

    Johannsen, D., Razgon, I. & Wahlström, M. 2009 Theory and Applications of Satisfiability Testing, SAT 2009 : 12th International Conference, SAT 2009. Kullmann, O. (ed.). Swansea, Wales, United Kingdom: Springer, Vol. 5584, p. 80-85 6 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  74. 2008
  75. Published

    A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances

    Wahlström, M. 1 May 2008 3rd International Workshop on Parameterized and Exact Computation (IWPEC 2008). Grohe, M. & Niedermeier, R. (eds.). Victoria (BC), Canada: Springer, Vol. 5018, p. 202-213 12 p. (Lecture Notes in Computer Science)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  76. 2005
  77. Published

    An Algorithm for the SAT Problem for Formulae of Linear Length

    Wahlström, M. 2005 ESA. p. 107-118 12 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  78. Published

    Counting models for 2SAT and 3SAT formulae

    Dahllöf, V., Jonsson, P. & Wahlström, M. 2005 In : Theoretical Computer Science. 332, 1-3, p. 265-291 27 p.

    Research output: Contribution to journalArticle

  79. Published

    Faster Exact Solving of SAT Formulae with a Low Number of Occurrences per Variable

    Wahlström, M. 2005 SAT. p. 309-323 15 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  80. 2004
  81. Published

    Exact algorithms for finding minimum transversals in rank-3 hypergraphs

    Wahlström, M. 2004 In : Journal of Algorithms. 51, 2, p. 107-121 15 p.

    Research output: Contribution to journalArticle

  82. 2002
  83. Published

    Counting Satisfying Assignments in 2-SAT and 3-SAT

    Dahllöf, V., Jonsson, P. & Wahlström, M. 2002 COCOON. p. 535-543 9 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution