1 citations · 1 across the 12 of their papers we have counts for
18 papers · 1 filter
High-Multiplicity Bin Packing is FPT
Tomohiro Koana, Soh Kumabe
Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with distinct it…
Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation
Tomohiro Koana, Soh Kumabe
Strong Connectivity Augmentation (SCA) asks whether a directed acyclic graph can be made strongly connected by adding at most prescribed links whose total weight is within a gi…
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
\textsc{-Packing} asks whether a graph contains vertex-disjoint copies of a fixed pattern graph . Via the standard reduction to \textsc{-Set Packing}, one obtains…
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…