3 citations · 7 across the 32 of their papers we have counts for
6 papers · 1 filter
Parameterized Algorithms for Maximum Cut with Connectivity Constraints
Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi +1
We study two variants of \textsc{Maximum Cut}, which we call \textsc{Connected Maximum Cut} and \textsc{Maximum Minimal Cut}, in this paper. In these problems, given an unweighted…
Computational Complexity of Hedonic Games on Sparse Graphs
Tesshu Hanaka, Hironori Kiya, Yasuhide Maei +1
The additively separable hedonic game (ASHG) is a model of coalition formation games on graphs. In this paper, we intensively and extensively investigate the computational complexi…
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi +4
We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus…
Independent Set Reconfiguration Parameterized by Modular-Width
Rémy Belmonte, Tesshu Hanaka, Michael Lampis +2
Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for g…
New Results on Directed Edge Dominating Set
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis +2
We study a family of generalizations of Edge Dominating Set on directed graphs called Directed -Edge Dominating Set. In this problem an arc is said to dominate itsel…
Parameterized Complexity of Safe Set
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis +3
In this paper we study the problem of finding a small safe set in a graph , i.e. a non-empty set of vertices such that no connected component of is adjacent to a larg…