Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Jana Holznigenkemper, Christian Komusiewicz, Nils Morawietz, and Bernhard Seeger. On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 54:1-54:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{holznigenkemper_et_al:LIPIcs.MFCS.2023.54, author = {Holznigenkemper, Jana and Komusiewicz, Christian and Morawietz, Nils and Seeger, Bernhard}, title = {{On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {54:1--54:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.54}, URN = {urn:nbn:de:0030-drops-185889}, doi = {10.4230/LIPIcs.MFCS.2023.54}, annote = {Keywords: Parameterized Complexity, Median String, Time Series, ETH} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Alexander Bille, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. A Graph-Theoretic Formulation of Exploratory Blockmodeling. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 14:1-14:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bille_et_al:LIPIcs.SEA.2023.14, author = {Bille, Alexander and Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils}, title = {{A Graph-Theoretic Formulation of Exploratory Blockmodeling}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {14:1--14:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.14}, URN = {urn:nbn:de:0030-drops-183648}, doi = {10.4230/LIPIcs.SEA.2023.14}, annote = {Keywords: Clustering, Exact Algorithms, ILP-Formulation, Branch-and-Bound, Social Networks} }
Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Christian Komusiewicz, Simone Linz, Nils Morawietz, and Jannik Schestag. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 18:1-18:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{komusiewicz_et_al:LIPIcs.CPM.2023.18, author = {Komusiewicz, Christian and Linz, Simone and Morawietz, Nils and Schestag, Jannik}, title = {{On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.18}, URN = {urn:nbn:de:0030-drops-179729}, doi = {10.4230/LIPIcs.CPM.2023.18}, annote = {Keywords: phylogenetic trees, parameterized complexity, tree distances, NNI, TBR} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Christian Komusiewicz and Nils Morawietz. Parameterized Local Search for Vertex Cover: When Only the Search Radius Is Crucial. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{komusiewicz_et_al:LIPIcs.IPEC.2022.20, author = {Komusiewicz, Christian and Morawietz, Nils}, title = {{Parameterized Local Search for Vertex Cover: When Only the Search Radius Is Crucial}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {20:1--20:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.20}, URN = {urn:nbn:de:0030-drops-173764}, doi = {10.4230/LIPIcs.IPEC.2022.20}, annote = {Keywords: Local Search, Structural parameterization, Fixed-parameter tractability} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Christian Komusiewicz and Nils Morawietz. Finding 3-Swap-Optimal Independent Sets and Dominating Sets Is Hard. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 66:1-66:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{komusiewicz_et_al:LIPIcs.MFCS.2022.66, author = {Komusiewicz, Christian and Morawietz, Nils}, title = {{Finding 3-Swap-Optimal Independent Sets and Dominating Sets Is Hard}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {66:1--66:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.66}, URN = {urn:nbn:de:0030-drops-168644}, doi = {10.4230/LIPIcs.MFCS.2022.66}, annote = {Keywords: Local Search, Graph problems, 3-swap neighborhood, PLS-completeness} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Nils Morawietz and Petra Wolf. A Timecop’s Chase Around the Table. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 77:1-77:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{morawietz_et_al:LIPIcs.MFCS.2021.77, author = {Morawietz, Nils and Wolf, Petra}, title = {{A Timecop’s Chase Around the Table}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {77:1--77:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.77}, URN = {urn:nbn:de:0030-drops-145176}, doi = {10.4230/LIPIcs.MFCS.2021.77}, annote = {Keywords: Time variable graph, Edge periodic cycle, Game of cops and robbers, Computational complexity} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. Colored Cut Games. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 30:1-30:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{morawietz_et_al:LIPIcs.FSTTCS.2020.30, author = {Morawietz, Nils and Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Sommer, Frank}, title = {{Colored Cut Games}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {30:1--30:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.30}, URN = {urn:nbn:de:0030-drops-132719}, doi = {10.4230/LIPIcs.FSTTCS.2020.30}, annote = {Keywords: Labeled Cut, Labeled Path, Network Robustness, Kernelization, PSPACE, Polynomial Hierarchy} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Nils Morawietz, Carolin Rehs, and Mathias Weller. A Timecop’s Work Is Harder Than You Think. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 71:1-71:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{morawietz_et_al:LIPIcs.MFCS.2020.71, author = {Morawietz, Nils and Rehs, Carolin and Weller, Mathias}, title = {{A Timecop’s Work Is Harder Than You Think}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {71:1--71:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.71}, URN = {urn:nbn:de:0030-drops-127404}, doi = {10.4230/LIPIcs.MFCS.2020.71}, annote = {Keywords: edge-periodic temporal graphs, cops and robbers, tally-intersection, congruence satisfyability} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 26:1-26:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{gruttemeier_et_al:LIPIcs.SWAT.2020.26, author = {Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils}, title = {{Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {26:1--26:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.26}, URN = {urn:nbn:de:0030-drops-122731}, doi = {10.4230/LIPIcs.SWAT.2020.26}, annote = {Keywords: Graph coloring, social networks, parameterized complexity, kernelization} }
Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. String Factorizations Under Various Collision Constraints. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 17:1-17:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{gruttemeier_et_al:LIPIcs.CPM.2020.17, author = {Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank}, title = {{String Factorizations Under Various Collision Constraints}}, booktitle = {31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-149-8}, ISSN = {1868-8969}, year = {2020}, volume = {161}, editor = {G{\o}rtz, Inge Li and Weimann, Oren}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.17}, URN = {urn:nbn:de:0030-drops-121428}, doi = {10.4230/LIPIcs.CPM.2020.17}, annote = {Keywords: NP-hard problem, fixed-parameter algorithms, collision-aware string partitioning} }
Feedback for Dagstuhl Publishing