3 citations · 7 across the 32 of their papers we have counts for
9 papers · 1 filter
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka +5
A cactus is a connected graph that does not contain as a minor. Given a graph and integer , Cactus Vertex Deletion (also known as Diamond Hitting Se…
Computing -Labeling with Combined Parameters
Tesshu Hanaka, Kazuma Kawai, Hirotaka Ono
Given a graph, an -labeling of the graph is an assignment from the vertex set to the set of nonnegative integers such that for any pair of vertices $(u,v),|f (u) - f (v…
Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability
Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi +1
We study the problem of finding a maximum cardinality minimal separator of a graph. This problem is known to be NP-hard even for bipartite graphs. In this paper, we strengthen this…
(In)approximability of Maximum Minimal FVS
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei +2
We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between…
Finding Diverse Trees, Paths, and More
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +1
Mathematical modeling is a standard approach to solve many real-world problems and {\em diversity} of solutions is an important issue, emerging in applying solutions obtained from…
Parameterized Complexity of -Path Packing
Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki +6
Given a graph , , and integers and , the \textsc{-Path Packing} problem asks to find vertex-disjoint paths of length that h…
Computing the Largest Bond and the Maximum Connected Cut of a Graph
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6
The cut-set of a graph is the set of edges that have one endpoint in and the other endpoint in , and whenever is connected…
A (probably) optimal algorithm for Bisection on bounded-treewidth graphs
Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the tot…
Hedonic Seat Arrangement Problems
Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke +3
In this paper, we study a variant of hedonic games, called \textsc{Seat Arrangement}. The model is defined by a bijection from agents with preferences for each other to vertices in…