Dr Magnus Wahlström

  1. 2018
  2. Forthcoming

    Path-contractions, edge deletions and connectivity preservation

    Gutin, Z., Ramanujan, M. S., Reidl, F. & Wahlstrom, M., 30 Oct 2018, (Accepted/In press) In : Journal of Computer and System Sciences.

    Research output: Contribution to journalArticle

  3. Forthcoming

    On r-Simple k-Path and Related Problems Parameterized by k/r

    Gutin, G., Wahlstrom, M. & Zehavi, M., 27 Sep 2018, (Accepted/In press) Proceedings of SODA 2019.

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

  4. Forthcoming

    Multi-budgeted directed cuts

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

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

  5. 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

  6. 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

  7. 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

  8. 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

  9. 2017
  10. 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

  11. 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

  12. Published

    The power of primitive positive definitions with polynomially many variables

    Lagerkvist, V. & Wahlstrom, M., 1 Jul 2017, In : Journal of Logic and Computation. 27, 5, p. 1465–1488 24 p.

    Research output: Contribution to journalArticle

  13. 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

  14. 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

  15. 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

  16. 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

  17. 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

  18. 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

  19. Published

    Parameterized Complexity of the Workflow Satisfiability Problem

    Cohen, D., Crampton, J., Gutin, Z. & Wahlstrom, M., 2017, Combinatorial Optimization and Graph Algorithms. Fukunaga, T. & Kawarabayashi, K. (eds.). Springer-Verlag, p. 101-120 20 p.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  20. 2016
  21. 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

  22. 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

  23. 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)

  24. 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

  25. 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

  26. 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

  27. 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

  28. 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

  29. 2015
  30. 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

  31. 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

  32. 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

  33. 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

  34. 2014
  35. 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

  36. Published

    Calculation of Discrepancy Measures and Applications

    Doerr, C., Gnewuch, M. & Wahlström, M., 2014, A Panorama of Discrepancy Theory. Chen, W., Srivastav, A. & Travaglini, G. (eds.). Springer, p. 621-678 58 p. (Lecture Notes in Mathematics; vol. 2107)

    Research output: Chapter in Book/Report/Conference proceedingChapter

  37. Forthcoming

    Clique cover and graph separation: New incompressibility results

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

    Research output: Contribution to journalArticle

  38. Forthcoming

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

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

    Research output: Contribution to journalArticle

  39. 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

  40. 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

  41. 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

  42. 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

  43. 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

  44. 2013
  45. 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

  46. 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

  47. 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

  48. 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

  49. 2012
  50. 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

  51. 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

  52. 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

  53. 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

  54. 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

  55. 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

  56. 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

  57. 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

  58. 2011
  59. 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

  60. Unpublished

    Hierarchies of Inefficient Kernelizability

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

    Research output: Contribution to journalArticle

  61. 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

  62. 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

  63. 2010
  64. 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

  65. 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

  66. 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

  67. 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

  68. 2009
  69. 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

  70. 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

  71. 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

  72. 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

  73. 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

  74. 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

  75. 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

  76. 2008
  77. 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

  78. 2005
  79. 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

  80. 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

  81. 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

  82. 2004
  83. 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

  84. 2002
  85. 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