Algorithms and Complexity

Filter
Conference contribution

Search results

  • 2024

    Another Hamiltonian Cycle in Bipartite Pfaffian Graphs

    Björklund, A., Kaski, P. & Nederlof, J., Jul 2024, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024. Bringmann, K., Grohe, M., Puppis, G. & Svensson, O. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 26. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 297).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Complexity Framework for Forbidden Subgraphs {IV:} The Steiner Forest Problem

    Bodlaender, H. L., Johnson, M. S., Martin, B., Oostveen, J., Pandey, S., Paulusma, D., Smith, S. & van Leeuwen, E. J., 22 Jun 2024, Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings. Springer, p. 206-217 (Lecture Notes in Computer Science; vol. 14764).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs

    Lozin, V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S. & van Leeuwen, E. J., 4 Dec 2024, 35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8-11, 2024, Sydney, Australia. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Vol. 322. p. 47:1-47:18

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs

    Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S. & van Leeuwen, E. J., 2024, 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024. Bodlaender, H. L. (ed.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, p. 29:1-29:17 29. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 294).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Exact and Parameterized Algorithms for Choosability

    Bliznets, I. & Nederlof, J., 2024, SOFSEM 2024: Theory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings. Fernau, H., Gaspers, S. & Klasing, R. (eds.). Springer, p. 111-124 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 14519 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Geometric Thickness of Multigraphs is ∃R-Complete

    Förster, H., Kindermann, P., Miltzow, T., Parada, I., Terziadis, S. & Vogtenhuber, B., 2024, LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I. Soto, J. A. & Wiese, A. (eds.). Springer, p. 336-349 14 p. (Lecture Notes in Computer Science; vol. 14578).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  • Large Language Models and the Extended Church-Turing Thesis

    Wiedermann, J. & van Leeuwen, J., 11 Sept 2024, Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024). Manea, F. & Pighizzini, G. (eds.). Göttingen, p. 198-213 16 p. (Electronic Proceedings in Theoretical Computer Science; vol. 407).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access

  • Separator Theorem and Algorithms for Planar Hyperbolic Graphs

    Kisfaludi-Bak, S., Masarìkovà, J., van Leeuwen, E. J., Walczak, B. & Wegrzycki, K., 2024, 40th International Symposium on Computational Geometry, SoCG 2024. Mulzer, W. & Phillips, J. M. (eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, p. 67:1-67:17 67. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 293).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters

    Groenland, C., Mannens, I., Nederlof, J., Piecyk, M. & Rzążewski, P., Jul 2024, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024. Bringmann, K., Grohe, M., Puppis, G. & Svensson, O. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 77. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 297).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
  • 2023

    Complexity Framework for Forbidden Subgraphs {III:}: When Problems Are Tractable on Subcubic Graphs

    Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S. & van Leeuwen, E. J., 21 Aug 2023, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023: MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. Leroux, J., Lombardy, S. & Peleg, D. (eds.). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, p. 57:1-57:15 57. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 272).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Computing Subset Vertex Covers in H-Free Graphs

    Brettell, N., Oostveen, J., Pandey, S., Paulusma, D. & van Leeuwen, E. J., 21 Sept 2023, Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings. Springer, p. 88-102 (Lecture Notes in Computer Science; vol. 14292).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Enumeration of Minimal Tropical Connected Sets

    Bliznets, I., Sagunov, D. & Tagin, E., 25 Apr 2023, Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings. Mavronicolas, M. (ed.). p. 127-141 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13898 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • MaxCut Above Guarantee

    Bliznets, I. & Epifanov, V., 21 Aug 2023, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leroux, J., Lombardy, S. & Peleg, D. (eds.). Dagstuhl Publishing, 14 p. 22. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 272).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

    Chalermsook, P., Fomin, F. V., Hamm, T., Korhonen, T., Nederlof, J. & Orgo, L., Sept 2023, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands. Gørtz, I. L., Farach-Colton, M., Puglisi, S. J. & Herman, G. (eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Vol. 274. p. 33:1-33:13 33. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 274).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

    Bergougnoux, B., Chekan, V., Ganian, R., Kanté, M. M., Mnich, M., Oum, S.-I., Pilipczuk, M. & van Leeuwen, E. J., Sept 2023, 31st Annual European Symposium on Algorithms, ESA 2023: ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands. Li Gortz, I., Farach-Colton, M., Puglisi, S. J. & Herman, G. (eds.). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, p. 18:1-18:18 18. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 274).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

    Bergougnoux, B., Chekan, V., Ganian, R., Kanté, M. M., Mnich, M., Oum, S.-I., Pilipczuk, M. & van Leeuwen, E. J., 30 Aug 2023, 31st Annual European Symposium on Algorithms, {ESA} 2023, September 4-6, 2023, Amsterdam, The Netherlands. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Vol. 274. p. 18:1-18:18 (LIPIcs).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • The Parameterised Complexity Of Integer Multicommodity Flow

    Mannens, I., Oostveen, J., van Leeuwen, E. J., Pandey, S. & Bodlaender, H. L., 13 Dec 2023, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Misra, N. & Wahlström, M. (eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, p. 91-109 6. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 285).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • The Power of Amortization on Scheduling with Explorable Uncertainty

    Liu, A., Liu, F.-H., Wong, P. W. H. & Zhang, X.-O., 22 Dec 2023, Approximation and Online Algorithms. Springer, 14 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Tight Lower Bounds for Problems Parameterized by Rank-Width

    Bergougnoux, B., Korhonen, T. & Nederlof, J., 1 Mar 2023, 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023. Berenbrink, P., Bouyer, P., Dawar, A. & Kanté, M. M. (eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Vol. 254. p. 11:1-11:17 11. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 254).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Treewidth Is NP-Complete on Cubic Graphs

    Bodlaender, H. L., Bonnet, É., Jaffke, L., Knop, D., Lima, P. T., Milanic, M., Ordyniak, S., Pandey, S. & Suchý, O., 2023, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Misra, N. & Wahlström, M. (eds.). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, Vol. 285. p. 7:1-7:13 13 p. 7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 285).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
  • 2022

    Few Induced Disjoint Paths for H-Free Graphs

    Martin, B., Paulusma, D., Smith, S. & van Leeuwen, E. J., 2022, Combinatorial Optimization - 7th International Symposium, ISCO 2022, Virtual Event, May 18-20, 2022, Revised Selected Papers. Ljubić, I., Barahona, F., Dey, S. S. & Mahjoub, A. R. (eds.). Springer, p. 89-101 13 p. (Lecture Notes in Computer Science; vol. 13526).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability

    Bodlaender, H. L., 22 Feb 2022, WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022, Proceedings. Mutzel, P., Rahman, M. S. & Slamin (eds.). 1 ed. Cham: Springer, p. 15-25 11 p. (Lecture Notes in Computer Science; vol. 13174 ).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

    Open Access
    File

  • Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

    Martin, B., Paulusma, D., Smith, S. & van Leeuwen, E. J., 2022, Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tubingen, Germany, June 22-24, 2022, Revised Selected Papers. Bekos, M. A. & Kaufmann, M. (eds.). Springer, p. 398-411 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13453 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Isolation Schemes for Problems on Decomposable Graphs

    Nederlof, J., Pilipczuk, M., Swennenhuis, C. M. F. & Wegrzycki, K., 2022, 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference). Berenbrink, P. & Monmege, B. (eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, p. 50:1-50:20 (Leibniz International Proceedings in Informatics; vol. 219).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • List Colouring Trees in Logarithmic Space

    Bodlaender, H. L., Groenland, C. & Jacob, H., 1 Sept 2022, 30th Annual European Symposium on Algorithms, ESA 2022. Chechik, S., Navarro, G., Rotenberg, E. & Herman, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 24:1-24:15 15 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 244).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • On Streaming Algorithms for Geometric Independent Set and Clique

    Oostveen, J., Klute, F. & Bhore, S., 21 Oct 2022, Approximation and Online Algorithms: 20th International Workshop, WAOA 2022, Potsdam, Germany, September 8–9, 2022, Proceedings. Chalermsook, P. & Laekhanukit, B. (eds.). 1 ed. Cham: Springer, p. 211-224 14 p. (Lecture Notes in Computer Science ; vol. 13538 ).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • On the Complexity of Problems on Tree-Structured Graphs

    Bodlaender, H. L., Groenland, C., Jacob, H., Pilipczuk, M. & Pilipczuk, M., 1 Dec 2022, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022. Dell, H. & Nederlof, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 6:1-6:17 17 p. 6. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 249).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • On the Parameterized Complexity of Computing Tree-Partitions

    Bodlaender, H. L., Groenland, C. & Jacob, H., 1 Dec 2022, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022. Dell, H. & Nederlof, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 7:1-7:20 20 p. 7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 249).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Pair Modeling: Does One Plus One Add Up?

    Stein Dani, V., ER, M., Koorn, J., van der Werf, J. M., Leopold, H. & Reijers, H., 24 Jan 2022, Business Process Management Workshops: BPM 2021 International Workshops, Rome, Italy, September 6–10, 2021, Revised Selected Papers. Marrella, A. & Weber, B. (eds.). Springer, p. 261-272 12 p. (Lecture Notes in Business Information Processing; vol. 436 LNBIP).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Parameterized Completeness Results for Bayesian Inference

    Bodlaender, H. L., Donselaar, N. & Kwisthout, J., 19 Sept 2022, International Conference on Probabilistic Graphical Models, PGM 2022, 5-7 October 2022, Almería, Spain. Salmerón, A. & Rumí, R. (eds.). PMLR, Vol. 186. p. 145-156 12 p. (Proceedings of Machine Learning Research).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Parameterized Complexity of Streaming Diameter and Connectivity Problems

    Oostveen, J. J. & Leeuwen, E. J. V., 1 Dec 2022, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Dell, H. & Nederlof, J. (eds.). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, p. 24:1-24:16 16 p. 24. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 249).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

    Bodlaender, H. L., Groenland, C., Nederlof, J. & Swennenhuis, C. M. F., 2022, Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021. IEEE, p. 193-204 12 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Problems Hard for Treewidth but Easy for Stable Gonality

    Bodlaender, H. L., Cornelissen, G. & Wegen, M. V. D., 1 Oct 2022, Graph-Theoretic Concepts in Computer Science: 48th International Workshop, WG 2022, Tübingen, Germany, June 22–24, 2022, Revised Selected Papers. Bekos, M. A. & Kaufmann, M. (eds.). 1 ed. Springer, p. 84-97 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13453 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • The Parameterized Complexity of the Survivable Network Design Problem

    Feldmann, A. E., Mukherjee, A. & van Leeuwen, E. J., 2022, Symposium on Simplicity in Algorithms (SOSA): 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022. Bringmann, K. & Chan, T. (eds.). SIAM, p. 37-56 20 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • The Power of Amortized Recourse for Online Graph Problems

    Liu, A. & Toole-Charignon, J., 21 Oct 2022, Approximation and Online Algorithms: 20th International Workshop, WAOA 2022, Potsdam, Germany, September 8–9, 2022, Proceedings. Chalermsook, P. & Laekhanukit, B. (eds.). 1 ed. Cham: Springer, p. 134–153 20 p. (Lecture Notes in Computer Science; vol. 13538).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

    Bodlaender, H. L., Groenland, C., Jacob, H., Jaffke, L. & Lima, P. T., 1 Dec 2022, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022. Dell, H. & Nederlof, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 8:1-8:18 18 p. 8. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 249).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
  • 2021

    A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

    Nederlof, J., Pawlewicz, J., Swennenhuis, C. M. F. & Wegrzycki, K., 2021, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021. Marx, D. (ed.). SIAM, p. 1682-1701 20 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • A Generic Convolution Algorithm for Join Operations on Tree Decompositions

    van Rooij, J., 28 Jun 2021, CSR 2021: Computer Science – Theory and Applications. Santhanam, R. & Musatov, D. (eds.). Springer, p. 435-459 25 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12730 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Disjoint Paths and Connected Subgraphs for H-Free Graphs.

    Kern, W., Martin, B., Paulusma, D., Smith, S. & Leeuwen, E. J. V., 2021, Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings. Flocchini, P. & Moura, L. (eds.). Springer, p. 414-427 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12757 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes

    Saitoh, T., Yoshinaka, R. & Bodlaender, H. L., 31 Jan 2021, WALCOM: Algorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 – March 2, 2021, Proceedings. Uehara, R., Hong, S.-H. & Nandy, S. C. (eds.). 1 ed. Cham: Springer, p. 142-153 12 p. (Lecture Notes in Computer Science ; vol. 12635 ).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors.

    Nederlof, J. & Wegrzycki, K., Jun 2021, STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. New York, United States: Association for Computing Machinery, p. 1670-1683

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem

    Mannens, I., Nederlof, J., Swennenhuis, C. & Szilágyi, K., 23 Jun 2021, Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021 Warsaw, Poland, June 23–25, 2021 Revised Selected Papers. Kowalik, L., Pilipczuk, M. & Rzazewski, P. (eds.). Springer, p. 52-79 28 p. (Lecture Notes in Computer Science; vol. 12911).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Parameterized complexities of dominating and independent set reconfiguration

    Bodlaender, H. L., Groenland, C. & Swennenhuis, C. M. F., 1 Nov 2021, 16th International Symposium on Parameterized and Exact Computation, IPEC 2021. Golovach, P. A. & Zehavi, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 9:1-9:16 16 p. 9. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 214).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation

    Bodlaender, H. L., 2021, Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Revised Selected Papers. Kowalik, L., Pilipczuk, M. & Rzazewski, P. (eds.). Springer, p. 15-27 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12911 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Streaming Deletion Problems Parameterized by Vertex Cover

    Oostveen, J. & van Leeuwen, E. J., 9 Sept 2021, Fundamentals of Computation Theory - 23rd International Symposium, FCT 2021, Athens, Greece, September 12-15, 2021, Proceedings. Bampis, E. & Pagourtzis, A. (eds.). Springer, p. 413-426 (Lecture Notes in Computer Science; vol. 12867).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • TORS: A train unit shunting and servicing simulator

    Van Der Linden, J. G. M., Mulderij, J., Huisman, B., Den Ouden, J. W., Van Den Akker, M., Hoogeveen, H. & De Weerdt, M. M., 2021, 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), p. 1773-1775 3 p. (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; vol. 3).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times

    Bienkowski, M., Kraska, A. & Liu, H.-H., 2 Jul 2021, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Bansal , N., Merelli , E. & Worrell , J. (eds.). Leibniz International Proceedings in Informatics (LIPIcs), p. 28:1-28:20 28. (LIPIcs; vol. 198).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
  • 2020

    Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

    Nederlof, J., 2020, Treewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Fomin, F. V., Kratsch, S. & Leeuwen, E. J. V. (eds.). Springer, p. 145-164 20 p. (Lecture Notes in Computer Science; vol. 12160).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Algorithms for the rainbow vertex coloring problem on graph classes

    Lima, P. T., van Leeuwen, E. J. & van der Wegen, M., 1 Aug 2020, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Esparza, J. & Kral, D. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 63:1--63:13 13 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 170).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File

  • Bipartite TSP in o(1.9999\8319) time, assuming quadratic time matrix multiplication

    Nederlof, J., 2020, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 40-53 14 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File