4 citations · 4 across the 3 of their papers we have counts for
7 papers
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…
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…
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…
Space-Efficient Algorithms for Longest Increasing Subsequence
Masashi Kiyomi, Hirotaka Ono, Yota Otachi +2
Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in time and space. Our goa…
The complexity of dominating set reconfiguration
Arash Haddadan, Takehiro Ito, Amer E. Mouawad +4
Suppose that we are given two dominating sets and of a graph whose cardinalities are at most a given threshold . Then, we are asked whether there exists a sequen…
Minimum Certificate Dispersal with Tree Structures
Taisuke Izumi, Tomoko Izumi, Hirotaka Ono +1
Given an n-vertex graph G=(V,E) and a set R \subseteq {{x,y} | x,y \in V} of requests, we consider to assign a set of edges to each vertex in G so that for every request {u, v} in…