Magnus Wahlström

Orcid: 0000-0002-0933-4504

Affiliations:
  • Royal Holloway, University of London, UK
  • Max Planck Institute for Informatics, Saarbrücken, Germany (former)


According to our database1, Magnus Wahlström authored at least 91 papers between 2002 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
On Weighted Graph Separation Problems and Flow Augmentation.
SIAM J. Discret. Math., March, 2024

Faster algorithms on linear delta-matroids.
CoRR, 2024

2023
<i>p</i>-Edge/vertex-connected vertex cover: Parameterized and approximation algorithms.
J. Comput. Syst. Sci., May, 2023

Preference swaps for the stable matching problem.
Theor. Comput. Sci., 2023

Representative set statements for delta-matroids and the Mader delta-matroid.
CoRR, 2023

Determinantal Sieving.
CoRR, 2023

Almost Consistent Systems of Linear Equations.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Parameterized Complexity of Equality MinCSP.
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022
The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems.
ACM Trans. Comput. Theory, 2022

Quasipolynomial Multicut-mimicking Networks and Kernels for Multiway Cut Problems.
ACM Trans. Algorithms, 2022

Many-visits TSP revisited.
J. Comput. Syst. Sci., 2022

On weighted graph separation problems and flow-augmentation.
CoRR, 2022

Component Order Connectivity in Directed Graphs.
Algorithmica, 2022

Directed flow-augmentation.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

On the Parameterized Complexity of Symmetric Directed Multicut.
Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

2021
<i>r</i>-Simple <i>k</i>-Path and Related Problems Parameterized by <i>k</i>/<i>r</i>.
ACM Trans. Algorithms, 2021

Randomized Contractions Meet Lean Decompositions.
ACM Trans. Algorithms, 2021

Parameterized Pre-Coloring Extension and List Coloring Problems.
SIAM J. Discret. Math., 2021

Solving hard cut problems via flow-augmentation.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020
Sparsification of SAT and CSP Problems via Tractable Extensions.
ACM Trans. Comput. Theory, 2020

Alternative parameterizations of Metric Dimension.
Theor. Comput. Sci., 2020

Representative Sets and Irrelevant Vertices: New Tools for Kernelization.
J. ACM, 2020

p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms.
CoRR, 2020

Multi-budgeted Directed Cuts.
Algorithmica, 2020

On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019
Path-contractions, edge deletions and connectivity preservation.
J. Comput. Syst. Sci., 2019

On r-Simple k-Path and Related Problems Parameterized by k/r.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Directed Multicut is W[1]-hard, Even for Four Terminal Pairs.
ACM Trans. Comput. Theory, 2018

Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials.
J. Comput. Syst. Sci., 2018

<i>k</i>-distinct in- and out-branchings in digraphs.
J. Comput. Syst. Sci., 2018

Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms?
CoRR, 2018

Parameterized Algorithms for Zero Extension and Metric Labelling Problems.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Euler Digraphs.
Proceedings of the Classes of Directed Graphs., 2018

2017
The power of primitive positive definitions with polynomially many variables.
J. Log. Comput., 2017

Rural postman parameterized by the number of components of required edges.
J. Comput. Syst. Sci., 2017

Odd properly colored cycles in edge-colored graphs.
Discret. Math., 2017

Acyclicity in edge-colored graphs.
Discret. Math., 2017

Chinese Postman Problem on edge-colored multigraphs.
Discret. Appl. Math., 2017

Randomization in Parameterized Complexity (Dagstuhl Seminar 17041).
Dagstuhl Reports, 2017

Kirchoff Matrices and Pfaffians to Design Deterministic Polynomial-Space Parameterized Algorithms.
CoRR, 2017

LP-branching algorithms based on biased graphs.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

k-Distinct In- and Out-Branchings in Digraphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra.
Proceedings of the Principles and Practice of Constraint Programming, 2017

2016
How to Generate Randomized Roundings with Dependencies and How to Derandomize Them.
Proceedings of the Algorithm Engineering - Selected Results and Surveys, 2016

Kernelization, Matroid Methods.
Encyclopedia of Algorithms, 2016

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems.
ACM Trans. Comput. Theory, 2016

On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations.
ACM Trans. Priv. Secur., 2016

On Problems as Hard as CNF-SAT.
ACM Trans. Algorithms, 2016

The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth.
SIAM J. Discret. Math., 2016

Half-integrality, LP-branching, and FPT Algorithms.
SIAM J. Comput., 2016

Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis.
Inf. Process. Lett., 2016

Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem.
Algorithmica, 2016

Directed multicut is <i>W</i>[1]-hard, even for four terminal pairs.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.
SIAM J. Discret. Math., 2015

A Completeness Theory for Polynomial (Turing) Kernelization.
Algorithmica, 2015

Bounded Bases of Strong Partial Clones.
Proceedings of the 2015 IEEE International Symposium on Multiple-Valued Logic, 2015

Structural Parameterizations of the Mixed Chinese Postman Problem.
Proceedings of the Algorithms - ESA 2015, 2015

2014
Clique Cover and Graph Separation: New Incompressibility Results.
ACM Trans. Comput. Theory, 2014

Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal.
ACM Trans. Algorithms, 2014

Randomized Rounding in the Presence of a Cardinality Constraint.
ACM J. Exp. Algorithmics, 2014

Parameterized Directed k-Chinese Postman Problem and k Arc-Disjoint Cycles Problem on Euler Digraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Half-integrality, LP-branching and FPT Algorithms.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Polynomially Closed Co-clones.
Proceedings of the IEEE 44th International Symposium on Multiple-Valued Logic, 2014

2013
Two edge modification problems without polynomial kernels.
Discret. Optim., 2013

Parameterized Rural Postman and Conjoining Bipartite Matching Problems.
CoRR, 2013

Parameterized Two-Player Nash Equilibrium.
Algorithmica, 2013

Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012
A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting.
SIAM J. Numer. Anal., 2012

Hardness of discrepancy computation and ε-net verification in high dimension.
J. Complex., 2012

Subexponential Parameterized Odd Cycle Transversal on Planar Graphs.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011
New Plain-Exponential Time Classes for Graph Homomorphism.
Theory Comput. Syst., 2011

On Problems as Hard as CNFSAT
CoRR, 2011

Hierarchies of Inefficient Kernelizability
CoRR, 2011

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

A Randomized Algorithm Based on Threshold Accepting to Approximate the Star Discrepancy
CoRR, 2011

Dependent Randomized Rounding: The Bipartite Case.
Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, 2011

2010
Algorithmic construction of low-discrepancy point sets via dependent randomized rounding.
J. Complex., 2010

Randomized Rounding for Routing and Covering Problems: Experiments and Improvements.
Proceedings of the Experimental Algorithms, 9th International Symposium, 2010

Preprocessing of Min Ones Problems: A Dichotomy.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009
Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences.
Proceedings of the Theory and Applications of Satisfiability Testing, 2009

A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

BBOB: Nelder-Mead with resize and halfruns.
Proceedings of the Genetic and Evolutionary Computation Conference, 2009

2008
A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances.
Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

2007
Algorithms, measures and upper bounds for satisfiability and related problems.
PhD thesis, 2007

2005
Counting models for 2SAT and 3SAT formulae.
Theor. Comput. Sci., 2005

Faster Exact Solving of SAT Formulae with a Low Number of Occurrences per Variable.
Proceedings of the Theory and Applications of Satisfiability Testing, 2005

An Algorithm for the SAT Problem for Formulae of Linear Length.
Proceedings of the Algorithms, 2005

2004
Exact algorithms for finding minimum transversals in rank-3 hypergraphs.
J. Algorithms, 2004

2002
Counting Satisfying Assignments in 2-SAT and 3-SAT.
Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002


  Loading...