3 citations · 12 across the 26 of their papers we have counts for
11 papers · 1 filter
Breaking the barrier for directed hamiltonicity
Tomohiro Koana, Soh Kumabe
We give a randomized algorithm for Directed Hamiltonian Cycle on -vertex directed graphs that runs in time. For general directed graphs, this is the first improv…
A Deterministic Polynomial Kernel for Odd Cycle Transversal
Tomohiro Koana, Soh Kumabe
We give a deterministic polynomial kernel for Odd Cycle Transversal, derandomizing the randomized kernel of Kratsch and Wahlström (TALG 2014). Our algorithm uses a deterministic po…
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…
Graph Coloring with Color Preferences
Tomohiro Koana, Yeeseok Oh, Hirotaka Yoneda
We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the colo…
Approximate Counting of -Paths in Time
Tomohiro Koana
We resolve the conjecture of Koutis and Williams that -paths can be approximately counted in time. For a simple directed graph with vertices and arcs, our ran…
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…
New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof +1
The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In…
Lawler-Moore Speedups via Additive Combinatorics
Karl Bringmann, Danny Hermelin, Tomohiro Koana +1
The Lawler-Moore dynamic programming framework is a classical tool in scheduling on parallel machines. It applies when the objective is regular, i.e. monotone in job completion tim…