Tomohiro Koana | DeepAI

AI Chat

Featured Co-authors

Rolf Niedermeier
71 publications
Fedor V. Fomin
59 publications
Petr A. Golovach
55 publications
Niclas Boehmer
32 publications
Eduard Eiben
27 publications
Christian Komusiewicz
25 publications
André Nichterlein
20 publications
Vincent Froese
19 publications
Magnus Wahlström
19 publications
Tanmay Inamdar
19 publications
Matthias Bentert
19 publications

∙ 08/29/2023

FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges

We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, th...

0 Fedor V. Fomin, et al. ∙

∙ 08/01/2023

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem

In this work, we study the Biclique-Free Vertex Deletion problem: Given ...

0 Lito Goldmann, et al. ∙

∙ 04/04/2023

Determinantal Sieving

We introduce determinantal sieving, a new, remarkably powerful tool in t...

0 Eduard Eiben, et al. ∙

∙ 02/01/2023

Parameterized Algorithms for Colored Clustering

In the Colored Clustering problem, one is asked to cluster edge-colored ...

0 Leon Kellerhals, et al. ∙

∙ 12/28/2022

Induced Matching below Guarantees: Average Paves the Way for Fixed-Parameter Tractability

In this work, we study the Induced Matching problem: Given an undirected...

0 Tomohiro Koana, et al. ∙

∙ 12/14/2022

Correlating Theory and Practice in Finding Clubs and Plexes

Finding large "cliquish" subgraphs is a classic NP-hard graph problem. I...

0 Aleksander Figiel, et al. ∙

∙ 11/13/2022

Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma

Given a graph and two integers k and ℓ, Partial Vertex Cover asks for a ...

0 Tomohiro Koana, et al. ∙

∙ 06/14/2022

The Complexity of Finding Fair Many-to-One Matchings

We analyze the (parameterized) computational complexity of "fair" varian...

0 Niclas Boehmer, et al. ∙

∙ 05/16/2022

Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences

We study stable matching problems where agents have multilayer preferenc...

0 Matthias Bentert, et al. ∙

∙ 03/11/2022

Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees

Vertex Cover parameterized by the solution size k is the quintessential ...

0 Leon Kellerhals, et al. ∙

∙ 01/14/2022

Covering Many (or Few) Edges with k Vertices in Sparse Graphs

We study the following two fixed-cardinality optimization problems (a ma...

0 Tomohiro Koana, et al. ∙

∙ 03/05/2021

Essentially Tight Kernels for (Weakly) Closed Graphs

We study kernelization of classic hard graph problems when the input gra...

0 Tomohiro Koana, et al. ∙

∙ 02/23/2021

A Refined Complexity Analysis of Fair Districting over Graphs

We study the NP-hard Fair Connected Districting problem: Partition a ver...

0 Niclas Boehmer, et al. ∙

∙ 02/17/2021

The Complexity of Gerrymandering Over Graphs: Paths and Trees

Roughly speaking, gerrymandering is the systematic manipulation of the b...

0 Matthias Bentert, et al. ∙

∙ 07/23/2020

Detecting and Enumerating Small Induced Subgraphs in c-Closed Graphs

Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called c-clo...

0 Tomohiro Koana, et al. ∙

∙ 07/10/2020

Computing Dense and Sparse Subgraphs of Weakly Closed Graphs

A graph G is weakly γ-closed if every induced subgraph of G contains one...

0 Tomohiro Koana, et al. ∙

∙ 05/29/2020

Parameterized Complexity of Min-Power Asymmetric Connectivity

We investigate parameterized algorithms for the NP-hard problem Min-Powe...

0 Matthias Bentert, et al. ∙

∙ 05/08/2020

Exploiting 𝐜-Closure in Kernelization Algorithms for Graph Problems

A graph is c-closed if every pair of vertices with at least c common nei...

0 Tomohiro Koana, et al. ∙

∙ 02/12/2020

Complexity of Combinatorial Matrix Completion With Diameter Constraints

We thoroughly study a novel and still basic combinatorial matrix complet...

0 Tomohiro Koana, et al. ∙

∙ 02/03/2020

Parameterized Algorithms for Matrix Completion With Radius Constraints

Considering matrices with missing entries, we study NP-hard matrix compl...

0 Tomohiro Koana, et al. ∙

∙ 01/09/2020

Parameterized Complexity of Geodetic Set

A vertex set S of a graph G is geodetic if every vertex of G lies on a s...

0 Leon Kellerhals, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world