Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
Matthias Bentert, Fedor V. Fomin, Fanny Hauser, and Saket Saurabh. The Parameterized Complexity Landscape of Two-Sets Cut-Uncut. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bentert_et_al:LIPIcs.IPEC.2024.14, author = {Bentert, Matthias and Fomin, Fedor V. and Hauser, Fanny and Saurabh, Saket}, title = {{The Parameterized Complexity Landscape of Two-Sets Cut-Uncut}}, booktitle = {19th International Symposium on Parameterized and Exact Computation (IPEC 2024)}, pages = {14:1--14:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-353-9}, ISSN = {1868-8969}, year = {2024}, volume = {321}, editor = {Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.14}, URN = {urn:nbn:de:0030-drops-222400}, doi = {10.4230/LIPIcs.IPEC.2024.14}, annote = {Keywords: Fixed-parameter tractability, Polynomial Kernels, W\lbrack1\rbrack-hardness, XP, para-NP-Hardness} }
Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
Kenneth Langedal, Matthias Bentert, Thorgal Blanco, and Pål Grønås Drange. PACE Solver Description: LUNCH - Linear Uncrossing Heuristics. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 34:1-34:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{langedal_et_al:LIPIcs.IPEC.2024.34, author = {Langedal, Kenneth and Bentert, Matthias and Blanco, Thorgal and Drange, P\r{a}l Gr{\o}n\r{a}s}, title = {{PACE Solver Description: LUNCH - Linear Uncrossing Heuristics}}, booktitle = {19th International Symposium on Parameterized and Exact Computation (IPEC 2024)}, pages = {34:1--34:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-353-9}, ISSN = {1868-8969}, year = {2024}, volume = {321}, editor = {Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.34}, URN = {urn:nbn:de:0030-drops-222608}, doi = {10.4230/LIPIcs.IPEC.2024.34}, annote = {Keywords: graph drawing, feedback arc set, algorithm engineering} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Matthias Bentert, Michael R. Fellows, Petr A. Golovach, Frances A. Rosamond, and Saket Saurabh. Breaking a Graph into Connected Components with Small Dominating Sets. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bentert_et_al:LIPIcs.MFCS.2024.24, author = {Bentert, Matthias and Fellows, Michael R. and Golovach, Petr A. and Rosamond, Frances A. and Saurabh, Saket}, title = {{Breaking a Graph into Connected Components with Small Dominating Sets}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.24}, URN = {urn:nbn:de:0030-drops-205801}, doi = {10.4230/LIPIcs.MFCS.2024.24}, annote = {Keywords: Parameterized Algorithms, Recursive Understanding, Polynomial Kernels, Degeneracy} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach, and Tuukka Korhonen. Two-Sets Cut-Uncut on Planar Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bentert_et_al:LIPIcs.ICALP.2024.22, author = {Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka}, title = {{Two-Sets Cut-Uncut on Planar Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.22}, URN = {urn:nbn:de:0030-drops-201654}, doi = {10.4230/LIPIcs.ICALP.2024.22}, annote = {Keywords: planar graphs, cut-uncut, group-constrained paths} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, and Blair D. Sullivan. Correlation Clustering with Vertex Splitting. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bentert_et_al:LIPIcs.SWAT.2024.8, author = {Bentert, Matthias and Crane, Alex and Drange, P\r{a}l Gr{\o}n\r{a}s and Reidl, Felix and Sullivan, Blair D.}, title = {{Correlation Clustering with Vertex Splitting}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {8:1--8:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8}, URN = {urn:nbn:de:0030-drops-200483}, doi = {10.4230/LIPIcs.SWAT.2024.8}, annote = {Keywords: graph modification, cluster editing, overlapping clustering, approximation, parameterized complexity} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf. Cluster Editing with Overlapping Communities. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.2, author = {Arrighi, Emmanuel and Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Sullivan, Blair D. and Wolf, Petra}, title = {{Cluster Editing with Overlapping Communities}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {2:1--2:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.2}, URN = {urn:nbn:de:0030-drops-194218}, doi = {10.4230/LIPIcs.IPEC.2023.2}, annote = {Keywords: graph modification, correlation clustering, vertex splitting, NP-hardness, parameterized algorithm} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Matthias Bentert, Jannik Schestag, and Frank Sommer. On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bentert_et_al:LIPIcs.IPEC.2023.4, author = {Bentert, Matthias and Schestag, Jannik and Sommer, Frank}, title = {{On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {4:1--4:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.4}, URN = {urn:nbn:de:0030-drops-194232}, doi = {10.4230/LIPIcs.IPEC.2023.4}, annote = {Keywords: Flexible graph connectivity, NP-hard problem, parameterized complexity, below-guarantee parameterization, treewidth} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Matthias Bentert, Klaus Heeger, and Tomohiro Koana. Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bentert_et_al:LIPIcs.ESA.2023.16, author = {Bentert, Matthias and Heeger, Klaus and Koana, Tomohiro}, title = {{Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {16:1--16:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.16}, URN = {urn:nbn:de:0030-drops-186692}, doi = {10.4230/LIPIcs.ESA.2023.16}, annote = {Keywords: FPT in P, Algebraic Algorithms, Adaptive Algorithms, Subgraph Detection, Matching, APSP} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a Geometric Lens to Find k Disjoint Shortest Paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bentert_et_al:LIPIcs.ICALP.2021.26, author = {Bentert, Matthias and Nichterlein, Andr\'{e} and Renken, Malte and Zschoche, Philipp}, title = {{Using a Geometric Lens to Find k Disjoint Shortest Paths}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {26:1--26:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.26}, URN = {urn:nbn:de:0030-drops-140954}, doi = {10.4230/LIPIcs.ICALP.2021.26}, annote = {Keywords: graph algorithms, dynamic programming, W\lbrack1\rbrack-hardness, geometry} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Matthias Bentert, Klaus Heeger, and Dušan Knop. Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bentert_et_al:LIPIcs.ISAAC.2020.36, author = {Bentert, Matthias and Heeger, Klaus and Knop, Du\v{s}an}, title = {{Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {36:1--36:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.36}, URN = {urn:nbn:de:0030-drops-133800}, doi = {10.4230/LIPIcs.ISAAC.2020.36}, annote = {Keywords: Edge-disjoint paths, pathwidth, feedback vertex number} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Matthias Bentert, Alexander Dittmann, Leon Kellerhals, André Nichterlein, and Rolf Niedermeier. An Adaptive Version of Brandes' Algorithm for Betweenness Centrality. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bentert_et_al:LIPIcs.ISAAC.2018.36, author = {Bentert, Matthias and Dittmann, Alexander and Kellerhals, Leon and Nichterlein, Andr\'{e} and Niedermeier, Rolf}, title = {{An Adaptive Version of Brandes' Algorithm for Betweenness Centrality}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {36:1--36:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.36}, URN = {urn:nbn:de:0030-drops-99846}, doi = {10.4230/LIPIcs.ISAAC.2018.36}, annote = {Keywords: network science, social network analysis, centrality measures, shortest paths, tree-like graphs, efficient pre- and postprocessing, FPT in P} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Matthias Bentert, Josef Malík, and Mathias Weller. Tree Containment With Soft Polytomies. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bentert_et_al:LIPIcs.SWAT.2018.9, author = {Bentert, Matthias and Mal{\'\i}k, Josef and Weller, Mathias}, title = {{Tree Containment With Soft Polytomies}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.9}, URN = {urn:nbn:de:0030-drops-88353}, doi = {10.4230/LIPIcs.SWAT.2018.9}, annote = {Keywords: Phylogenetics, Reticulation-Visible Networks, Multifurcating Trees} }
Feedback for Dagstuhl Publishing