1 citations · 1 across the 16 of their papers we have counts for
16 papers
Moving Geometric Objects to Render Their Intersection Graph Connected or Locally Dense
Tesshu Hanaka, Nicolás Honorato-Droguett, Hirotaka Ono +2
In this paper, we study graph editing problems on geometric intersection graphs. For a tuple of geometric objects in some Euclidean space, let $G_\mat…
Multi-Winner Voting with Argumentative Ballots
Ryuta Arisaka, Hirotaka Ono
We introduce multi-winner voting with argumentative ballots (MVArg) and investigate theoretical properties. As our conceptual contribution, we generalise approval ballots to argume…
A Moderatorless Protocol for WEREWOLF
Naoki Kitamura, Hironori Kiya, Hirotaka Ono
Social deduction games, or hidden-role games, are multiplayer games in which players are assigned private roles and act under asymmetric information about other players' roles and…
Arrow-Type Impossibility for Genuinely Modal Judgments
Yutaka Nagai, Hirotaka Ono
Judgment aggregation studies how to combine individual judgments on logically related propositions into a collective judgment. Classical impossibility results show that sufficientl…
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…
The Complexity of Maximal/Closed Frequent Tree Mining for Bounded Height Trees
Kenta Komoto, Kazuhiro Kurita, Hirotaka Ono
Frequent tree mining asks us to enumerate tree patterns that occur frequently in a database of rooted trees. This problem is motivated by tree-structured data in bioinformatics, su…
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…
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…
An improved spectral lower bound of treewidth
Tatsuya Gima, Tesshu Hanaka, Kohei Noro +2
We show that for every -vertex graph with at least one edge, its treewidth is greater than or equal to , where and are the maximum degree a…
Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover
Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono +2
The uniqueness of an optimal solution to a combinatorial optimization problem attracts many fields of researchers' attention because it has a wide range of applications, it is rela…
Algorithms for Optimally Shifting Intervals under Intersection Graph Models
Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka +1
We introduce Geometric Graph Edit Distance, a model for modifying geometric intersection graphs by moving objects. The objective is to obtain a graph in a prescribed class while mi…
Structural Parameterizations of Vertex Integrity
Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi +3
The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a sma…
Winner Determination Algorithms for Graph Games with Matching Structures
Tesshu Hanaka, Hironori Kiya, Hirotaka Ono +1
Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a mat…