3 citations · 4 across the 6 of their papers we have counts for
9 papers
Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
Tomohiro Koana, Nidhi Purohit, Kirill Simonov
In Clique Cover, given a graph and an integer , the task is to partition the vertices of into cliques. Clique Cover on unit ball graphs has a natural interpretation…
Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma
Tomohiro Koana, André Nichterlein, Niklas Wünsche
Given a graph and two integers and , Partial Vertex Cover asks for a set of at most vertices whose deletion results in a graph with at most edges. Based on the…
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
Matthias Bentert, Niclas Boehmer, Klaus Heeger +1
We study stable matching problems where agents have multilayer preferences: There are layers each consisting of one preference relation for each agent. Recently, Chen et al.…
Essentially Tight Kernels for (Weakly) Closed Graphs
Tomohiro Koana, Christian Komusiewicz, Frank Sommer
We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closu…
The Complexity of Gerrymandering Over Graphs: Paths and Trees
Matthias Bentert, Tomohiro Koana, Rolf Niedermeier
Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. Whi…
Detecting and Enumerating Small Induced Subgraphs in -Closed Graphs
Tomohiro Koana, André Nichterlein
Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called -closure, for a parameterized study of clique enumeration problems. A graph is -closed if every pair of…