13 papers
Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi +4
Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world probl…
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…
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…
Algorithms for Optimally Shifting Intervals under Intersection Graph Models
Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka +1
In well-studied graph modification problems, adding and deleting vertices and edges are used as graph editing operations. We propose a model for graph modification on geometric int…
Game-Theoretic and Algorithmic Analyses of Multi-Agent Routing under Crossing Costs
Tesshu Hanaka, Nikolaos Melissinos, Hirotaka Ono
Coordinating the movement of multiple autonomous agents over a shared network is a fundamental challenge in algorithmic robotics, intelligent transportation, and distributed system…
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…