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 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Aleksander Figiel, Tomohiro Koana, André Nichterlein, and Niklas Wünsche. Correlating Theory and Practice in Finding Clubs and Plexes. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 47:1-47:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{figiel_et_al:LIPIcs.ESA.2023.47, author = {Figiel, Aleksander and Koana, Tomohiro and Nichterlein, Andr\'{e} and W\"{u}nsche, Niklas}, title = {{Correlating Theory and Practice in Finding Clubs and Plexes}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {47:1--47:18}, 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.47}, URN = {urn:nbn:de:0030-drops-187000}, doi = {10.4230/LIPIcs.ESA.2023.47}, annote = {Keywords: Preprocessing, Turing kernelization, Pearson correlation coefficient} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Tomohiro Koana. FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 46:1-46:8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.MFCS.2023.46, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Koana, Tomohiro}, title = {{FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {46:1--46:8}, 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.46}, URN = {urn:nbn:de:0030-drops-185806}, doi = {10.4230/LIPIcs.MFCS.2023.46}, annote = {Keywords: Partial Vertex Cover, Approximation Algorithms, Max Cut} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Tomohiro Koana. Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 39:1-39:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{koana:LIPIcs.STACS.2023.39, author = {Koana, Tomohiro}, title = {{Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {39:1--39:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.39}, URN = {urn:nbn:de:0030-drops-176914}, doi = {10.4230/LIPIcs.STACS.2023.39}, annote = {Keywords: Parameterized Complexity, Below Guarantees, Induced Matching, Gallai-Edmonds Decomposition} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Leon Kellerhals, Tomohiro Koana, and Pascal Kunz. Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 19:1-19:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2022.19, author = {Kellerhals, Leon and Koana, Tomohiro and Kunz, Pascal}, title = {{Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {19:1--19:14}, 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.19}, URN = {urn:nbn:de:0030-drops-173758}, doi = {10.4230/LIPIcs.IPEC.2022.19}, annote = {Keywords: parameterized complexity, vertex cover, feedback vertex set, above guarantee parameterization} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Niclas Boehmer and Tomohiro Koana. The Complexity of Finding Fair Many-To-One Matchings. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 27:1-27:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{boehmer_et_al:LIPIcs.ICALP.2022.27, author = {Boehmer, Niclas and Koana, Tomohiro}, title = {{The Complexity of Finding Fair Many-To-One Matchings}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {27:1--27:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.27}, URN = {urn:nbn:de:0030-drops-163680}, doi = {10.4230/LIPIcs.ICALP.2022.27}, annote = {Keywords: Graph theory, polynomial-time algorithms, NP-hardness, FPT, ILP, color coding, submodular and supermodular functions, algorithmic fairness} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer. Covering Many (Or Few) Edges with k Vertices in Sparse Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 42:1-42:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{koana_et_al:LIPIcs.STACS.2022.42, author = {Koana, Tomohiro and Komusiewicz, Christian and Nichterlein, Andr\'{e} and Sommer, Frank}, title = {{Covering Many (Or Few) Edges with k Vertices in Sparse Graphs}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {42:1--42:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.42}, URN = {urn:nbn:de:0030-drops-158525}, doi = {10.4230/LIPIcs.STACS.2022.42}, annote = {Keywords: Parameterized Complexity, Kernelization, Partial Vertex Cover, Densest k-Subgraph, Max (k,n-k)-Cut, Degeneracy} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Essentially Tight Kernels For (Weakly) Closed Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 35:1-35:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{koana_et_al:LIPIcs.ISAAC.2021.35, author = {Koana, Tomohiro and Komusiewicz, Christian and Sommer, Frank}, title = {{Essentially Tight Kernels For (Weakly) Closed Graphs}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.35}, URN = {urn:nbn:de:0030-drops-154681}, doi = {10.4230/LIPIcs.ISAAC.2021.35}, annote = {Keywords: Fixed-parameter tractability, kernelization, c-closure, weak \gamma-closure, Independent Set, Induced Matching, Connected Vertex Cover, Ramsey numbers, Dominating Set} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Leon Kellerhals, Tomohiro Koana, André Nichterlein, and Philipp Zschoche. The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 26:1-26:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2021.26, author = {Kellerhals, Leon and Koana, Tomohiro and Nichterlein, Andr\'{e} and Zschoche, Philipp}, title = {{The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {26:1--26:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.26}, URN = {urn:nbn:de:0030-drops-154096}, doi = {10.4230/LIPIcs.IPEC.2021.26}, annote = {Keywords: Correlation Clustering, Cluster Editing, Algorithm Engineering, FPT, Kernelization, Heuristics} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Tomohiro Koana, Vincent Froese, and Rolf Niedermeier. Binary Matrix Completion Under Diameter Constraints. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 47:1-47:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{koana_et_al:LIPIcs.STACS.2021.47, author = {Koana, Tomohiro and Froese, Vincent and Niedermeier, Rolf}, title = {{Binary Matrix Completion Under Diameter Constraints}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {47:1--47:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.47}, URN = {urn:nbn:de:0030-drops-136925}, doi = {10.4230/LIPIcs.STACS.2021.47}, annote = {Keywords: sunflowers, binary matrices, Hamming distance, stringology, consensus problems, complexity dichotomy, combinatorial algorithms, graph factors, 2-Sat, Hamming radius} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Leon Kellerhals and Tomohiro Koana. Parameterized Complexity of Geodetic Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 20:1-20:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2020.20, author = {Kellerhals, Leon and Koana, Tomohiro}, title = {{Parameterized Complexity of Geodetic Set}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.20}, URN = {urn:nbn:de:0030-drops-133237}, doi = {10.4230/LIPIcs.IPEC.2020.20}, annote = {Keywords: NP-hard graph problems, Shortest paths, Tree-likeness, Parameter hierarchy, Data reduction, Integer linear programming} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing Dense and Sparse Subgraphs of Weakly Closed Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 20:1-20:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{koana_et_al:LIPIcs.ISAAC.2020.20, author = {Koana, Tomohiro and Komusiewicz, Christian and Sommer, Frank}, title = {{Computing Dense and Sparse Subgraphs of Weakly Closed Graphs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {20:1--20:17}, 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.20}, URN = {urn:nbn:de:0030-drops-133646}, doi = {10.4230/LIPIcs.ISAAC.2020.20}, annote = {Keywords: Fixed-parameter tractability, c-closure, degeneracy, clique relaxations, bicliques, dominating set} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-Closure in Kernelization Algorithms for Graph Problems. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 65:1-65:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{koana_et_al:LIPIcs.ESA.2020.65, author = {Koana, Tomohiro and Komusiewicz, Christian and Sommer, Frank}, title = {{Exploiting c-Closure in Kernelization Algorithms for Graph Problems}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {65:1--65:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.65}, URN = {urn:nbn:de:0030-drops-129316}, doi = {10.4230/LIPIcs.ESA.2020.65}, annote = {Keywords: Fixed-parameter tractability, kernelization, c-closure, Dominating Set, Induced Matching, Irredundant Set, Ramsey numbers} }
Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Tomohiro Koana, Vincent Froese, and Rolf Niedermeier. Parameterized Algorithms for Matrix Completion with Radius Constraints. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 20:1-20:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{koana_et_al:LIPIcs.CPM.2020.20, author = {Koana, Tomohiro and Froese, Vincent and Niedermeier, Rolf}, title = {{Parameterized Algorithms for Matrix Completion with Radius Constraints}}, booktitle = {31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)}, pages = {20:1--20: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.20}, URN = {urn:nbn:de:0030-drops-121456}, doi = {10.4230/LIPIcs.CPM.2020.20}, annote = {Keywords: fixed-parameter tractability, consensus string problems, Closest String, Closest String with Wildcards} }
Feedback for Dagstuhl Publishing