Matthias Mnich

According to our database1, Matthias Mnich authored at least 66 papers between 2009 and 2020.

Collaborative distances:



In proceedings 
PhD thesis 


Online presence:



Voting and Bribing in Single-Exponential Time.
ACM Trans. Economics and Comput., 2020

Time- and Space-optimal Algorithm for the Many-visits TSP.
ACM Trans. Algorithms, 2020

Dynamic Parameterized Problems and Algorithms.
ACM Trans. Algorithms, 2020

Odd Multiway Cut in Directed Acyclic Graphs.
SIAM J. Discret. Math., 2020

Combinatorial n-fold integer programming and applications.
Math. Program., 2020

On the complexity of solving a decision problem with flow-depending costs: The case of the IJsselmeer dikes.
Discret. Optim., 2020

Recent Advances in Practical Data Reduction.
CoRR, 2020

A 3/2-Approximation for the Metric Many-visits Path TSP.
CoRR, 2020

Dense Steiner problems: Approximation algorithms and inapproximability.
CoRR, 2020

Stable Matchings with Covering Constraints: A Complete Computational Trichotomy.
Algorithmica, 2020

Solving Packing Problems with Few Small Items Using Rainbow Matchings.
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Hitting Long Directed Cycles Is Fixed-Parameter Tractable.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Engineering Kernelization for Maximum Cut.
Proceedings of the Symposium on Algorithm Engineering and Experiments, 2020

Domination When the Stars Are Out.
ACM Trans. Algorithms, 2019

Single Machine Batch Scheduling to Minimize the Weighted Number of Tardy Jobs.
CoRR, 2019

Degree-Bounded Generalized Polymatroids and Approximating the Metric Many-Visits TSP.
CoRR, 2019

Multitype Integer Monoid Optimization and Applications.
CoRR, 2019

Resolving Infeasibility of Linear Systems: A Parameterized Approach.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set.
Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

New algorithms for maximum disjoint paths based on tree-likeness.
Math. Program., 2018

Big data algorithms beyond machine learning.
Künstliche Intell., 2018

Improved bounds for minimal feedback vertex sets in tournaments.
J. Graph Theory, 2018

Improved integrality gap upper bounds for traveling salesperson problems with distances one and two.
Eur. J. Oper. Res., 2018

Linear-time recognition of map graphs with outerplanar witness.
Discret. Optim., 2018

New deterministic algorithms for solving parity games.
Discret. Optim., 2018

Time- and space-optimal algorithms for the many-visits TSP.
CoRR, 2018

Parameterized complexity of machine scheduling: 15 open problems.
Comput. Oper. Res., 2018

Linear Kernels and Linear-Time Algorithms for Finding Large Cuts.
Algorithmica, 2018

Reachability Switching Games.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

New Approximation Algorithms for (1, 2)-TSP.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A Unifying Framework for Manipulation Problems.
Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

Large Independent Sets in Triangle-Free Planar Graphs.
SIAM J. Discret. Math., 2017

Polynomial kernels for weighted problems.
J. Comput. Syst. Sci., 2017

Polynomial kernels for deletion to classes of acyclic digraphs.
Discret. Optim., 2017

Stable Marriage with Covering Constraints-A Complete Computational Trichotomy.
Proceedings of the Algorithmic Game Theory - 10th International Symposium, 2017

Parameterized complexity dichotomy for Steiner Multicut.
J. Comput. Syst. Sci., 2016

Lower Bounds for Locally Highly Connected Graphs.
Graphs Comb., 2016

Large Independent Sets in Subquartic Planar Graphs.
Proceedings of the WALCOM: Algorithms and Computation - 10th International Workshop, 2016

On Routing Disjoint Paths in Bounded Treewidth Graphs.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

A 7/3-Approximation for Feedback Vertex Sets in Tournaments.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Interval scheduling and colorful independent sets.
J. Sched., 2015

Scheduling and fixed-parameter tractability.
Math. Program., 2015

Max-Cut Parameterized Above the Edwards-Erdős Bound.
Algorithmica, 2015

When Does Schwartz Conjecture Hold?
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Beyond Max-Cut: λ-extendible properties parameterized above the Poljak-Turzík bound.
J. Comput. Syst. Sci., 2014

Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs.
Algorithmica, 2014

Treewidth Computation and Kernelization in the Parallel External Memory Model.
Proceedings of the Theoretical Computer Science, 2014

Kernel and fast algorithm for dense triplet inconsistency.
Theor. Comput. Sci., 2013

Feedback Vertex Sets in Tournaments.
J. Graph Theory, 2013

Scheduling Meets Fixed-Parameter Tractability.
CoRR, 2013

Improved integrality gap upper bounds for TSP with distances one and two.
CoRR, 2013

Induced Matchings in Subcubic Planar Graphs.
SIAM J. Discret. Math., 2012

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables.
J. Comput. Syst. Sci., 2012

Bisections above Tight Lower Bounds.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

Parameterized Complexity of Induced H-Matching on Claw-Free Graphs.
Proceedings of the Algorithms - ESA 2012, 2012

A linear kernel for a planar connected dominating set.
Theor. Comput. Sci., 2011

Book review.
Oper. Res. Lett., 2011

Planar k-Path in Subexponential Time and Polynomial Space.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

Betweenness parameterized above tight lower bound.
J. Comput. Syst. Sci., 2010

All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Polynomial Kernels
CoRR, 2010

Ranking and Drawing in Subexponential Time.
Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables.
Proceedings of the Algorithms, 2010

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.
Theory Comput. Syst., 2009

Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks.
J. Bioinform. Comput. Biol., 2009

Ordinal Embedding Relaxations Parameterized Above Tight Lower Bound
CoRR, 2009