3 citations · 7 across the 32 of their papers we have counts for
6 papers · 1 filter
Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
Tesshu Hanaka, Yuto Okada, Yota Otachi +1
We study the parameterized complexity of the problems of finding a maximum common (induced) subgraph of two given graphs. Since these problems generalize several NP-complete proble…
Finding a HIST: Chordality, Structural Parameters, and Diameter
Tesshu Hanaka, Hironori Kiya, Hirotaka Ono
A homeomorphically irreducible spanning tree (HIST) is a spanning tree with no degree-2 vertices, serving as a structurally minimal backbone of a graph. While the existence of HIST…
Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion
Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka +2
Removing overlaps is a central task in domains such as scheduling, visibility, and map labelling. This can be modelled using graphs, where overlap removals correspond to enforcing…
Structural Parameters for Steiner Orientation
Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos +3
We consider the \textsc{Steiner Orientation} problem, where we are given as input a mixed graph and a set of demand pairs , . The goal is to ori…
Broadcasting under Structural Restrictions
Yudai Egami, Tatsuya Gima, Tesshu Hanaka +7
In the Telephone Broadcast problem we are given a graph with a designated source vertex . Our goal is to transmit a message, which is initially known only to ,…
On the Complexity of Minimising the Moving Distance for Dispersing Objects
Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka +1
We study Geometric Graph Edit Distance (GGED), a graph-editing model to compute the minimum edit distance of intersection graphs that uses moving objects as an edit operation. We f…