If you made any changes in Pure these will be visible here soon.

Research Output 2009 2018

  • 29 Conference article in proceeding
  • 27 Article
  • 1 Book/Film/Article review
  • 1 Doctoral Thesis
2018

Big data algorithms beyond machine learning

Mnich, M., Feb 2018, In : Künstliche Intelligenz. 32, 1, p. 9-17 9 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access

Improved bounds for minimal feedback vertex sets in tournaments

Mnich, M. & Teutrine, E-L., Jul 2018, In : Journal of Graph Theory. 88, 3, p. 482-506 25 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access

Improved integrality gap upper bounds for traveling salesperson problems with distances one and two

Mnich, M. & Momke, T., 16 Apr 2018, In : European Journal of Operational Research. 266, 2, p. 436-457 22 p.

Research output: Contribution to journalArticleAcademicpeer-review

Linear Kernels and Linear-Time Algorithms for Finding Large Cuts

Etscheid, M. & Mnich, M., Sep 2018, In : Algorithmica. 80, 9, p. 2574-2615 42 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access

Linear-time recognition of map graphs with outerplanar witness

Mnich, M., Rutter, I. & Schmidt, J. M., 1 May 2018, In : Discrete Optimization. 28, p. 63-77 15 p.

Research output: Contribution to journalArticleAcademicpeer-review

New algorithms for maximum disjoint paths based on tree-likeness

Fleszar, K., Mnich, M. & Spoerhase, J., 1 Sep 2018, In : Mathematical Programming. 171, 1-2, p. 433-461 29 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access

New deterministic algorithms for solving parity games

Mnich, M., Roglin, H. & Rosner, C., 1 Nov 2018, In : Discrete Optimization. 30, p. 73-95 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

Parameterized complexity of machine scheduling: 15 open problems

Mnich, M. & van Bevern, R., 1 Dec 2018, In : Computers & Operations Research. 100, p. 254-261 8 p.

Research output: Contribution to journalArticleAcademicpeer-review

2017

Dynamic parameterized problems and algorithms

Alman, J., Mnich, M. & Vassilevska Williams, V., 2017, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Dagstuhl, Germany: Schloss Dagstuhl, Vol. 80. p. 41:1--41:16 41. (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Improved bounds for minimal feedback vertex sets in tournaments

Mnich, M. & Teutrine, E-L., 2017, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Schloss Dagstuhl, p. 24:1-24:10 (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 63).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Open Access

Large Independent Sets in Triangle-Free Planar Graphs

Dvorak, Z. & Mnich, M., Jun 2017, In : Siam Journal on Discrete Mathematics. 31, 2, p. 1355-1373 19 p.

Research output: Contribution to journalArticleAcademicpeer-review

Polynomial Kernels for Deletion to Classes of Acyclic Digraphs

Mnich, M. & van Leeuwen, E. J., Aug 2017, In : Discrete Optimization. 25, C, p. 48-76 29 p.

Research output: Contribution to journalArticleAcademicpeer-review

Polynomial kernels for weighted problems

Etscheid, M., Kratsch, S., Mnich, M. & Röglin, H., Mar 2017, In : Journal of Computer and System Sciences. 84, p. 1-10 10 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access

Stable Marriage with Covering Constraints: A Complete Computational Trichotomy

Mnich, M. & Schlotter, I., 2017, Algorithmic Game Theory. SAGT 2017. Springer, p. 320-332 (Lecture Notes in Computer Science, Vol. 10504).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Voting and Bribing in Single-Exponential Time

Knop, D., Koutecký, M. & Mnich, M., 2017, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Dagstuhl, Germany: Schloss Dagstuhl, Vol. 66. p. 46:1-46:14 46. (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

2016
1 Citation (Scopus)
46 Downloads (Pure)

A 7/3-Approximation for Feedback Vertex Sets in Tournaments

Mnich, M., Vassilevska Williams, V. & Végh, L. A., 2016, 24th Annual European Symposium on Algorithms (ESA 2016). Sankowski, P. & Zaroliagis, C. (eds.). Dagstuhl: Schloss Dagstuhl, Vol. 57. p. 67:1-67:14 14 p. 67. (Leibniz International Proceedings in Informatics).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Open Access
File

Large Independent Sets in Subquartic Planar Graphs

Mnich, M., 2016, WALCOM: Algorithms and Computation: 10th International Workshop, WALCOM 2016 Kathmandu, Nepal March 29-31, 2016 Proceedings. Kaykobad, M. & Petreschi, R. (eds.). Springer, p. 209-221 (Lecture Notes in Computer Science (LNCS), Vol. 9627).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Linear Kernels and Linear-Time Algorithms for Finding Large Cuts

Etscheid, M. & Mnich, M., 2016, 27th International Symposium on Algorithms and Computation (ISAAC 2016). Schloss Dagstuhl, (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 64).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Open Access

Linear-Time Recognition of Map Graphs with Outerplanar Witness

Mnich, M., Rutter, I. & Schmidt, J. M., 2016, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Pagh, R. (ed.). Schloss Dagstuhl, p. 5:1–5:14 (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 53).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Lower bounds for locally highly connected graphs

Adamaszek, A., Adamaszek, M., Mnich, M. & Schmidt, J. M., Sep 2016, In : Graphs and Combinatorics. 32, 5, p. 1641-1650 10 p.

Research output: Contribution to journalArticleAcademicpeer-review

New deterministic algorithms for solving parity games

Mnich, M., Röglin, H. & Rösner, C., 2016, LATIN 2016: Theoretical Informatics. Springer, p. 634-645 (Lecture Notes in Computer Science, Vol. 9644).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

On Routing Disjoint Paths in Bounded Treewidth Graphs

Ene, A., Mnich, M., Pilipczuk, M. & Risteski, A., 2016, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016): Proceedings of a meeting held 22-24 June 2016, Reykjavik, Iceland.. Pagh, R. (ed.). Schloss Dagstuhl, p. 15:1–15:15 (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 53).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Parameterized complexity dichotomy for Steiner multicut

Bringmann, K., Hermelin, D., Mnich, M. & van Leeuwen, E. J., Sep 2016, In : Journal of Computer and System Sciences. 82, 6, p. 1020-1043 24 p.

Research output: Contribution to journalArticleAcademicpeer-review

2015

Interval scheduling and colorful independent sets

van Bevern, R., Mnich, M., Niedermeier, R. & Weller, M., 2015, In : Journal of Scheduling. 18, 5, p. 449-469

Research output: Contribution to journalArticleAcademicpeer-review

Max-Cut parameterized above the Edwards-Erdős bound

Crowston, R., Jones, M. & Mnich, M., 2015, In : Algorithmica. 72, 3, p. 734-757

Research output: Contribution to journalArticleAcademicpeer-review

Parameterized Complexity Dichotomy for Steiner Multicut

Bringmann, K., Hermelin, D., Mnich, M. & van Leeuwen, E. J., 2015, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Schloss Dagstuhl, Vol. 30. p. 157-170 (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 30).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Open Access

Polynomial Kernels for Weighted Problems

Etscheid, M., Kratsch, S., Mnich, M. & Röglin, H., 2015, Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015 Milan, Italy, August 24-28, 2015, Proceedings Part II. Italiano, G. F., Pighizzini, G. & Sannella, D. T. (eds.). Springer, p. 287-298 (Lecture Notes in Computer Science (LNCS), Vol. 9235).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Scheduling and fixed-parameter tractability

Mnich, M. & Wiese, A., 2015, In : Mathematical Programming. 154, 1-2, p. 533-562

Research output: Contribution to journalArticleAcademicpeer-review

When Does Schwartz' Conjecture Hold?

Mnich, M., Raj Shrestha, Y. & Yang, Y., 2015, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015). p. 603-609

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Open Access
2014

Beyond Max-Cut: λ-extendible properties parameterized above Poljak-Turzík bound

Mnich, M., Philip, G., Saurabh, S. & Suchy, O., 2014, In : Journal of Computer and System Sciences. 80, 7, p. 1384-1403

Research output: Contribution to journalArticleAcademicpeer-review

Large Independent Sets in Triangle-Free Planar Graphs

Dvorak, Z. & Mnich, M., 2014, Algorithms - ESA 2014: 22nd Annual European Symposium Wroclaw, Poland, September 8-10, 2014 Proceedings. Schulz, A. S. & Wagner, D. (eds.). Springer, p. 346-357 (Lecture Notes in Computer Science (LNCS), Vol. 8737).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Parameterized complexity of induced graph matching on claw-free graphs.

Hermelin, D., Mnich, M. & van Leeuwen, E. J., 2014, In : Algorithmica. 70, 3, p. 513-560

Research output: Contribution to journalArticleAcademicpeer-review

Scheduling and Fixed-Parameter Tractability

Mnich, M. & Wiese, A., 2014, Integer Programming and Combinatorial Optimization: 17th International Conference, IPCO 2014 Bonn, Germany, June 23-25, 2014 Proceedings. Lee, J. & Vygen, J. (eds.). Springer, p. 381-392 (Lecture Notes in Computer Science, Vol. 8494).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems

Fernau, H., Fomin, F. V., Lokshtanov, D., Mnich, M., Philip, G. & Saurabh, S., 2014, In : Tsinghua Science and Technology. 19, 4, p. 374-386

Research output: Contribution to journalArticleAcademicpeer-review

Treewidth Computation and Kernelization in the Parallel External Memory Model

Jacob, R., Lieber, T. & Mnich, M., 2014, Theoretical Computer Science: 8th IFIP TC1/WG 2.2 International Conference, TCS 2014, Rome, Italy, September 1-3, 2014 Proceedings. Diaz, J., Lanese, I. & Sangiorgi, D. (eds.). Springer, p. 78-89 (Lecture Notes in Computer Science, Vol. 8705).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

2013

Feedback vertex sets in tournaments

Gaspers, S. & Mnich, M., 2013, In : Journal of Graph Theory. 72, 1, p. 72-89

Research output: Contribution to journalArticleAcademicpeer-review

Kernel and fast algorithm for dense triplet inconsistency

Guillemot, S. & Mnich, M., 2013, In : Theoretical Computer Science. 494, p. 134-143

Research output: Contribution to journalArticleAcademicpeer-review

2012

Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzík Bound

Mnich, M., Philip, G., Saurabh, S. & Suchy, O., 2012, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Schloss Dagstuhl, p. 412-423 (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 18).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Open Access

Bisections Above Tight Lower Bounds

Mnich, M. & Zenklusen, R., 2012, Graph-Theoretic Concepts in Computer Science: 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers. Springer, p. 184-193 (Lecture Notes in Computer Science, Vol. 7551).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables

Gutin, G., van Iersel, L., Mnich, M. & Yeo, A., 2012, In : Journal of Computer and System Sciences. 78, 1, p. 151-163

Research output: Contribution to journalArticleAcademicpeer-review

Induced matchings in subcubic planar graphs

Kang, R. J., Mnich, M. & Müller, T., 2012, In : Siam Journal on Discrete Mathematics. 26, 3, p. 1383-1411

Research output: Contribution to journalArticleAcademicpeer-review

Interval Scheduling and Colorful Independent Sets

van Bevern, R., Mnich, M., Niedermeier, R. & Weller, M., 2012, Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 2012 Proceedings. Chao, K-M., Hsu, T. & Lee, D-T. (eds.). Springer, Vol. 7676. p. 247-256 (Lecture Notes in Computer Science, Vol. 7676).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Max-Cut Parameterized above the Edwards-Erdős Bound

Crowston, R., Jones, M. & Mnich, M., 2012, Automata, Languages and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 2012, Proceedings, Part I. Czumaj, A., Mehlhorn, K., Pitts, A. & Wattenhofer, R. (eds.). Springer, p. 242-253 (Lecture Notes in Computer Science, Vol. 7391).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Parameterized Complexity of Induced H-Matching on Claw-Free Graphs

Hermelin, D., Mnich, M. & van Leeuwen, E. J., 2012, Algorithms - ESA 2012: 20th Annual European Symposium Ljubljana, Slovenia, September 2012 Proceedings. Epstein, L. & Ferragina, P. (eds.). Springer, p. 624-635 (Lecture Notes in Computer Science, Vol. 7501).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

2011

A linear kernel for a planar connected dominating set

Lokshtanov, D., Mnich, M. & Saurabh, S., 2011, In : Theoretical Computer Science. 412, 23, p. 2536-2543

Research output: Contribution to journalArticleAcademicpeer-review

Domination when the stars are out

Hermelin, D., Mnich, M., van Leeuwen, E. J. & Woeginger, G. J., 2011, Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. Springer, p. 462-473 (Lecture Notes in Computer Science, Vol. 6755).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Exact Exponential Algorithms

Mnich, M., 2011, In : Operations Research Letters. 39, 3, p. 229-230

Research output: Contribution to journalBook/Film/Article reviewAcademic

Planar k-Path in Subexponential Time and Polynomial Space

Lokshtanov, D., Mnich, M. & Saurabh, S., 2011, Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011 Tepla Monastery, Czech Republic, June 2011 Revised Papers. Kolman, P. & Kratochvil, J. (eds.). Springer, p. 262-270 (Lecture Notes in Computer Science, Vol. 6986).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Ranking and Drawing in Subexponential Time

Fernau, H., Fomin, F. V., Lokshtanov, D., Mnich, M., Philip, G. & Saurabh, S., 2011, Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers. Iliopoulos, C. S. & Smyth, W. F. (eds.). Springer, p. 337-348 (Lecture Notes in Computer Science, Vol. 6460).

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

2010

Algorithms in Moderately Exponential Time

Mnich, M., 2010, 216 p.

Research output: ThesisDoctoral ThesisExternal