From the 3 of 11 linked papers with an AI index.
1 citations · 1 across the 7 of their papers we have counts for
10 papers · 1 filter
Complexity of induced subgraph isomorphism and maximum common induced subgraph parameterized by cluster vertex deletion number
Tomohiro Koana, Soh Kumabe, Yota Otachi
We study the parameterized complexity of Induced Subgraph Isomorphism (ISI) and Maximum Common Induced Subgraph (MCIS) with respect to the cluster vertex deletion number . For I…
A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation
Tomohiro Koana, Soh Kumabe
We study restricted-link augmentation to -vertex-connectivity. An instance consists of a graph , possibly disconnected, a set of admissible links on its vertices, integer…
Kernelization for -Packing Revisited
Tomohiro Koana, Soh Kumabe
The paper investigates kernelization for the H‑Packing problem, providing improved polynomial kernels for various subdivided‑star patterns and proving compression lower bounds for…
Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi +4
Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world probl…
On the Complexity of the Matching Problem of Regular Expressions with Backreferences
Soh Kumabe, Yuya Uezato
ReDoS is a well-known type of algorithmic complexity attack, where an adversary supplies maliciously crafted strings to a regular expression matching engine, aiming to exhaust comp…
Quadratic Kernel for Cliques or Trees Vertex Deletion
Soh Kumabe
We consider \textsc{Cliques or Trees Vertex Deletion}, which is a hybrid of two fundamental parameterized problems: \textsc{Cluster Vertex Deletion} and \textsc{Feedback Vertex Set…