List of publications

2021

  1. Dvořák, P., Eiben, E., Ganian, R., Knop, D., & Ordyniak, S. (2021). The complexity landscape of decompositional parameters for ILP: Programs with few global variables and constraints. Artif. Intell., 300, 103561. https://doi.org/10.1016/j.artint.2021.103561
  2. Knop, D. (2021). Local linear set on graphs with bounded twin cover number. Inf. Process. Lett., 170, 106118. https://doi.org/10.1016/j.ipl.2021.106118
  3. Dvořák, P., Feldmann, A. E., Knop, D., Masařík, T., Toufar, T., & Veselý, P. (2021). Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. SIAM J. Discret. Math., 35(1), 546–574. https://doi.org/10.1137/18M1209489
  4. Chaplick, S., Fomin, F. V., Golovach, P. A., Knop, D., & Zeman, P. (2021). Kernelization of Graph Hamiltonicity: Proper H-Graphs. SIAM J. Discret. Math., 35(2), 840–892. https://doi.org/10.1137/19M1299001
  5. Klavı́k Pavel, Knop, D., & Zeman, P. (2021). Graph isomorphism restricted by lists. Theor. Comput. Sci., 860, 51–71. https://doi.org/10.1016/j.tcs.2021.01.027
  6. Bredereck, R., Figiel, A., Kaczmarczyk, A., Knop, D., & Niedermeier, R. (2021). High-Multiplicity Fair Allocation Made More Practical. In F. Dignum, A. Lomuscio, U. Endriss, & A. Nowé (Eds.), AAMAS ’21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021 (pp. 260–268). ACM. https://dl.acm.org/doi/10.5555/3463952.3463988

2020

  1. Knop, D. (2020). Partitioning graphs into induced subgraphs. Discret. Appl. Math., 272, 31–42. https://doi.org/10.1016/j.dam.2019.01.010
  2. Knop, D., Koutecký, M., & Mnich, M. (2020). Combinatorial n-fold integer programming and applications. Math. Program., 184(1), 1–34. https://doi.org/10.1007/s10107-019-01402-2
  3. Bulteau, L., Hermelin, D., Knop, D., Labarre, A., & Vialette, S. (2020). The Clever Shopper Problem. Theory Comput. Syst., 64(1), 17–34. https://doi.org/10.1007/s00224-019-09917-z
  4. Knop, D., Koutecký, M., & Mnich, M. (2020). Voting and Bribing in Single-Exponential Time. ACM Trans. Economics and Comput., 8(3), 12:1–12:28. https://doi.org/10.1145/3396855
  5. Knop, D., Pilipczuk, M., & Wrochna, M. (2020). Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. ACM Trans. Comput. Theory, 12(3), 19:1–19:19. https://doi.org/10.1145/3397484
  6. Bredereck, R., Chen, J., Knop, D., Luo, J., & Niedermeier, R. (2020). Adapting Stable Matchings to Evolving Preferences. The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, 1830–1837. https://aaai.org/ojs/index.php/AAAI/article/view/5550
  7. Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Knop, D., & Niedermeier, R. (2020). Parameterized Algorithms for Finding a Collective Set of Items. The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, 1838–1845. https://aaai.org/ojs/index.php/AAAI/article/view/5551
  8. Boehmer, N., Bredereck, R., Knop, D., & Luo, J. (2020). Fine-Grained View on Bribery for Group Identification. In C. Bessiere (Ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 (pp. 67–73). ijcai.org. https://doi.org/10.24963/ijcai.2020/10
  9. Bentert, M., Heeger, K., & Knop, D. (2020). Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters. In Y. Cao, S.-W. Cheng, & M. Li (Eds.), 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference) (Vol. 181, pp. 36:1–36:14). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2020.36
  10. Chaplick, S., Golovach, P. A., Hartmann, T. A., & Knop, D. (2020). Recognizing Proper Tree-Graphs. In Y. Cao & M. Pilipczuk (Eds.), 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference) (Vol. 180, pp. 8:1–8:15). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2020.8
  11. Husek, R., Knop, D., & Masařík, T. (2020). Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View. In Y. Cao & M. Pilipczuk (Eds.), 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference) (Vol. 180, pp. 16:1–16:18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2020.16
  12. Klavı́k Pavel, Knop, D., & Zeman, P. (2020). Graph Isomorphism Restricted by Lists. In I. Adler & H. Müller (Eds.), Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers (Vol. 12301, pp. 106–118). Springer. https://doi.org/10.1007/978-3-030-60440-0_9
  13. Bredereck, R., Heeger, K., Knop, D., & Niedermeier, R. (2020). Multidimensional Stable Roommates with Master List. In X. Chen, N. Gravin, M. Hoefer, & R. Mehta (Eds.), Web and Internet Economics - 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings (Vol. 12495, pp. 59–73). Springer. https://doi.org/10.1007/978-3-030-64946-3_5

2019

  1. Altmanová, K., Knop, D., & Koutecký, M. (2019). Evaluating and Tuning n-fold Integer Programming. ACM J. Exp. Algorithmics, 24(1), 2.2:1–2.2:22. https://doi.org/10.1145/3330137
  2. Knop, D., Koutecký, M., Masařík, T., & Toufar, T. (2019). Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity. Log. Methods Comput. Sci., 15(4). https://doi.org/10.23638/LMCS-15(4:12)2019
  3. Eiben, E., Ganian, R., Knop, D., & Ordyniak, S. (2019). Solving Integer Quadratic Programming via Explicit and Structural Restrictions. The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, 1477–1484. https://doi.org/10.1609/aaai.v33i01.33011477
  4. Bredereck, R., Kaczmarczyk, A., Knop, D., & Niedermeier, R. (2019). High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming. In A. Karlin, N. Immorlica, & R. Johari (Eds.), Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019 (pp. 505–523). ACM. https://doi.org/10.1145/3328526.3329649
  5. Eiben, E., Ganian, R., Knop, D., Ordyniak, S., Pilipczuk, M., & Wrochna, M. (2019). Integer Programming and Incidence Treedepth. In A. Lodi & V. Nagarajan (Eds.), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings (Vol. 11480, pp. 194–204). Springer. https://doi.org/10.1007/978-3-030-17953-3_15
  6. Bredereck, R., Heeger, K., Knop, D., & Niedermeier, R. (2019). Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters. In P. Lu & G. Zhang (Eds.), 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China (Vol. 149, pp. 44:1–44:14). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2019.44
  7. Knop, D., Masařík, T., & Toufar, T. (2019). Parameterized Complexity of Fair Vertex Evaluation Problems. In P. Rossmanith, P. Heggernes, & J.-P. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany (Vol. 138, pp. 33:1–33:16). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2019.33
  8. Eiben, E., Knop, D., Panolan, F., & Suchý, O. (2019). Complexity of the Steiner Network Problem with Respect to the Number of Terminals. In R. Niedermeier & C. Paul (Eds.), 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany (Vol. 126, pp. 25:1–25:17). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2019.25
  9. Knop, D., Pilipczuk, M., & Wrochna, M. (2019). Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. In R. Niedermeier & C. Paul (Eds.), 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany (Vol. 126, pp. 44:1–44:15). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2019.44
  10. Chaplick, S., Fomin, F. V., Golovach, P. A., Knop, D., & Zeman, P. (2019). Kernelization of Graph Hamiltonicity: Proper H-Graphs. In Z. Friggstad, J.-R. Sack, & M. R. Salavatipour (Eds.), Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings (Vol. 11646, pp. 296–310). Springer. https://doi.org/10.1007/978-3-030-24766-9_22

2018

  1. Dvořák, P., & Knop, D. (2018). Parameterized Complexity of Length-bounded Cuts and Multicuts. Algorithmica, 80(12), 3597–3617. https://doi.org/10.1007/s00453-018-0408-7
  2. Knop, D., & Masařík, T. (2018). Computational complexity of distance edge labeling. Discret. Appl. Math., 246, 80–98. https://doi.org/10.1016/j.dam.2017.01.007
  3. Fiala Jirı́, Gavenciak, T., Knop, D., Koutecký, M., & Kratochvı́l Jan. (2018). Parameterized complexity of distance labeling and uniform channel assignment problems. Discret. Appl. Math., 248, 46–55. https://doi.org/10.1016/j.dam.2017.02.010
  4. Knop, D., & Koutecký, M. (2018). Scheduling meets n-fold integer programming. J. Sched., 21(5), 493–503. https://doi.org/10.1007/s10951-017-0550-0
  5. Knop, D., Koutecký, M., & Mnich, M. (2018). A Unifying Framework for Manipulation Problems. In E. André, S. Koenig, M. Dastani, & G. Sukthankar (Eds.), Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018 (pp. 256–264). International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM. http://dl.acm.org/citation.cfm?id=3237427
  6. Eiben, E., Ganian, R., Knop, D., & Ordyniak, S. (2018). Unary Integer Linear Programming with Structural Restrictions. In J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden (pp. 1284–1290). ijcai.org. https://doi.org/10.24963/ijcai.2018/179
  7. Dvořák, P., Knop, D., & Toufar, T. (2018). Target Set Selection in Dense Graph Classes. In W.-L. Hsu, D.-T. Lee, & C.-S. Liao (Eds.), 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan (Vol. 123, pp. 18:1–18:13). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2018.18
  8. Gavenciak, T., Knop, D., & Koutecký, M. (2018). Integer Programming in Parameterized Complexity: Three Miniatures. In C. Paul & M. Pilipczuk (Eds.), 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland (Vol. 115, pp. 21:1–21:16). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2018.21
  9. Dvořák, P., Feldmann, A. E., Knop, D., Masařík, T., Toufar, T., & Veselý, P. (2018). Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. In R. Niedermeier & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France (Vol. 96, pp. 26:1–26:15). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2018.26
  10. Altmanová, K., Knop, D., & Koutecký, M. (2018). Evaluating and Tuning n-fold Integer Programming. In G. D’Angelo (Ed.), 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L’Aquila, Italy (Vol. 103, pp. 10:1–10:14). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SEA.2018.10

2017

  1. Folwarczný, L., & Knop, D. (2017). IV-matching is strongly NP-hard. Inf. Process. Lett., 125, 5–8. https://doi.org/10.1016/j.ipl.2017.04.014
  2. Knop, D., Koutecký, M., & Mnich, M. (2017). Combinatorial n-fold Integer Programming and Applications. In K. Pruhs & C. Sohler (Eds.), 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria (Vol. 87, pp. 54:1–54:14). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2017.54
  3. Dvořák, P., Eiben, E., Ganian, R., Knop, D., & Ordyniak, S. (2017). Solving Integer Linear Programs with a Small Number of Global Variables and Constraints. In C. Sierra (Ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017 (pp. 607–613). ijcai.org. https://doi.org/10.24963/ijcai.2017/85
  4. Knop, D. (2017). Partitioning Graphs into Induced Subgraphs. In F. Drewes, Martı́n-Vide Carlos, & B. Truthe (Eds.), Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings (Vol. 10168, pp. 338–350). https://doi.org/10.1007/978-3-319-53733-7_25
  5. Knop, D., Koutecký, M., & Mnich, M. (2017). Voting and Bribing in Single-Exponential Time. In H. Vollmer & B. Vallée (Eds.), 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany (Vol. 66, pp. 46:1–46:14). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2017.46
  6. Knop, D., Koutecký, M., Masařík, T., & Toufar, T. (2017). Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity. In H. L. Bodlaender & G. J. Woeginger (Eds.), Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers (Vol. 10520, pp. 344–357). Springer. https://doi.org/10.1007/978-3-319-68705-6_26

2016

  1. Fiala Jirı́, Gavenciak, T., Knop, D., Koutecký, M., & Kratochvı́l Jan. (2016). Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems - (Extended Abstract). In T. N. Dinh & M. T. Thai (Eds.), Computing and Combinatorics - 22nd International Conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings (Vol. 9797, pp. 67–78). Springer. https://doi.org/10.1007/978-3-319-42634-1_6

2015

  1. Knop, D., & Masařík, T. (2015). Computational Complexity of Distance Edge Labeling. In Z. Lipták & W. F. Smyth (Eds.), Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers (Vol. 9538, pp. 287–298). Springer. https://doi.org/10.1007/978-3-319-29516-9_24
  2. Dvorak, P., & Knop, D. (2015). Parametrized Complexity of Length-Bounded Cuts and Multi-cuts. In R. Jain, S. Jain, & F. Stephan (Eds.), Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings (Vol. 9076, pp. 441–452). Springer. https://doi.org/10.1007/978-3-319-17142-5_37