26 papers · 1 filter
On the Complexity of Secluded Path Problems
Tesshu Hanaka, Daisuke Tsuru
This paper investigates the complexity of finding secluded paths in graphs. We focus on the \textsc{Short Secluded Path} problem and a natural new variant we introduce, \textsc{Sho…
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…
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…
On the complexity of finding a spanning even tree in a graph
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +4
A tree is said to be even if for every pair of distinct leaves, the length of the unique path between them is even. In this paper we discuss the problem of determining whether an i…