8 citations · 36 across the 49 of their papers we have counts for
5 papers · 1 filter
Linear-Time Recognition of Double-Threshold Graphs
Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi +1
A graph is a double-threshold graph if there exist a vertex-weight function and two real numbers s…
Low-Congestion Shortcut and Graph Parameters
Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi +1
The concept of low-congestion shortcuts is initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologi…
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…
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…